22 #ifndef TESSERACT_CCUTIL_GENERICHEAP_H_
23 #define TESSERACT_CCUTIL_GENERICHEAP_H_
57 template <
typename Pair>
87 const Pair&
get(
int index)
const {
96 int hole_index = heap_.
size();
102 *entry = heap_.
back();
103 hole_index = SiftUp(hole_index, *entry);
104 heap_[hole_index] = *entry;
119 int new_size = heap_.
size() - 1;
122 if (entry !=
nullptr)
127 Pair hole_pair = heap_[new_size];
129 int hole_index = SiftDown(0, hole_pair);
130 heap_[hole_index] = hole_pair;
142 if (worst_index < 0)
return false;
144 if (entry !=
nullptr)
145 *entry = heap_[worst_index];
146 int heap_size = heap_.
size() - 1;
149 Pair hole_pair = heap_[heap_size];
150 int hole_index = SiftUp(worst_index, hole_pair);
151 heap_[hole_index] = hole_pair;
159 int heap_size = heap_.
size();
160 if (heap_size == 0)
return -1;
165 int worst_index = heap_size - 1;
166 int end_parent = ParentNode(worst_index);
167 for (
int i = worst_index - 1; i > end_parent; --i) {
168 if (heap_[worst_index] < heap_[i]) worst_index = i;
183 int index = pair - &heap_[0];
184 Pair hole_pair = heap_[index];
185 index = SiftDown(index, hole_pair);
186 index = SiftUp(index, hole_pair);
187 heap_[index] = hole_pair;
194 int SiftUp(
int hole_index,
const Pair& pair) {
196 while (hole_index > 0 && pair < heap_[parent = ParentNode(hole_index)]) {
197 heap_[hole_index] = heap_[parent];
206 int SiftDown(
int hole_index,
const Pair& pair) {
207 int heap_size = heap_.
size();
209 while ((child = LeftChild(hole_index)) < heap_size) {
210 if (child + 1 < heap_size && heap_[child + 1] < heap_[child])
212 if (heap_[child] < pair) {
213 heap_[hole_index] = heap_[child];
224 int ParentNode(
int index)
const {
225 return (index + 1) / 2 - 1;
227 int LeftChild(
int index)
const {
228 return index * 2 + 1;
237 #endif // TESSERACT_CCUTIL_GENERICHEAP_H_