1 // heap.h 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // 16 // \file 17 // Implementation of a heap as in STL, but allows tracking positions 18 // in heap using a key. The key can be used to do an in place update of 19 // values in the heap. 20 21 #ifndef FST_LIB_HEAP_H__ 22 #define FST_LIB_HEAP_H__ 23 24 #include <functional> 25 #include <vector> 26 27 namespace fst { 28 29 // 30 // \class Heap 31 // \brief A templated heap implementation that support in place update 32 // of values. 33 // 34 // The templated heap implementation is a little different from the 35 // STL priority_queue and the *_heap operations in STL. The heap 36 // supports indexing of values in the heap via an associated key. 37 // 38 // Each value is internally associated with a key which is returned 39 // to the calling functions on heap insert. This key can be used 40 // to later update the specific value in the heap. 41 // 42 // \param T the element type of the hash, can be POD, Data or Ptr to Data 43 // \param Compare Comparison class for determing min-heapness of max-heapness 44 // 45 static const int kNoKey = -1; 46 template <class T, class Compare> 47 class Heap { 48 public: 49 50 // initialize with a specific comparator Heap(Compare comp)51 Heap(Compare comp) : comp_(comp), size_(0) { } 52 53 // Create a heap with initial size of internal arrays of 1024 Heap()54 Heap() : size_(0) { } 55 ~Heap()56 ~Heap() { } 57 58 // insert a value into the heap Insert(const T & val)59 int Insert(const T& val) { 60 if (size_ < (int)A_.size()) { 61 A_[size_] = val; 62 pos_[key_[size_]] = size_; 63 } else { 64 A_.push_back(val); 65 pos_.push_back(size_); 66 key_.push_back(size_); 67 } 68 69 ++size_; 70 return Insert(val, size_ - 1); 71 } 72 73 // update a value at position given by the key. The pos array is first 74 // indexed by the key. The position gives the position in the heap array. 75 // Once we have the position we can then use the standard heap operations 76 // to calculate the parent and child positions. Update(int key,const T & val)77 void Update(int key, const T& val) { 78 int i = pos_[key]; 79 if (comp_(val, A_[Parent(i)])) { 80 Insert(val, i); 81 } else { 82 A_[i] = val; 83 Heapify(i); 84 } 85 } 86 87 // pop the (best/worst) from the heap Pop()88 T Pop() { 89 T max = A_[0]; 90 91 Swap(0, size_-1); 92 size_--; 93 Heapify(0); 94 return(max); 95 } 96 97 // return value of best in heap Top()98 T Top() const { 99 return A_[0]; 100 } 101 102 // check if the heap is empty Empty()103 bool Empty() const { 104 return(size_ == 0); 105 } 106 Clear()107 void Clear() { 108 size_ = 0; 109 } 110 111 112 // 113 // The following protected routines is used in a supportive role 114 // for managing the heap and keeping the heap properties. 115 // 116 private: 117 // compute left child of parent Left(int i)118 int Left(int i) { 119 return 2*(i+1)-1; // 0 -> 1, 1 -> 3 120 } 121 122 // compute right child of parent Right(int i)123 int Right(int i) { 124 return 2*(i+1); // 0 -> 2, 1 -> 4 125 } 126 127 // given a child compute parent Parent(int i)128 int Parent(int i) { 129 return (i-1)/2; // 1 -> 0, 2 -> 0, 3 -> 1, 4-> 1 130 } 131 132 // swap a child, parent. Use to move element up/down tree 133 // note a little tricky here. When we swap we need to swap 134 // the value 135 // the associated keys 136 // the position of the value in the heap Swap(int j,int k)137 void Swap(int j, int k) { 138 int tkey = key_[j]; 139 pos_[key_[j] = key_[k]] = j; 140 pos_[key_[k] = tkey] = k; 141 142 T val = A_[j]; 143 A_[j] = A_[k]; 144 A_[k] = val; 145 } 146 147 148 // heapify subtree rooted at index i. Heapify(int i)149 void Heapify(int i) { 150 int l = Left(i); 151 int r = Right(i); 152 int largest; 153 154 if (l < size_ && comp_(A_[l], A_[i]) ) 155 largest = l; 156 else 157 largest = i; 158 159 if (r < size_ && comp_(A_[r], A_[largest]) ) 160 largest = r; 161 162 if (largest != i) { 163 Swap(i, largest); 164 Heapify(largest); 165 } 166 } 167 168 169 // insert(update) element at subtree rooted at index i Insert(const T & val,int i)170 int Insert(const T& val, int i) { 171 int p; 172 while (i > 0 && !comp_(A_[p = Parent(i)], val)) { 173 Swap(i, p); 174 i = p; 175 } 176 177 return key_[i]; 178 } 179 180 181 private: 182 Compare comp_; 183 184 vector<int> pos_; 185 vector<int> key_; 186 vector<T> A_; 187 int size_; 188 189 // DISALLOW_EVIL_CONSTRUCTORS(Heap); 190 }; 191 192 } 193 194 #endif // FST_LIB_HEAP_H__ 195