10 #ifndef BINARYHEAP_HPP
11 #define BINARYHEAP_HPP
14 #define BINARYHEAP_CHECK 0
18 # define CHECK_CONSISTY() this->CheckConsistency()
21 # define CHECK_CONSISTY() ;
65 this->data.reserve(initial_capacity);
84 size_t child = gap * 2;
87 while (child <= this->
items) {
89 if (child < this->
items && *this->data[child + 1] < *this->data[child]) {
93 if (!(*this->data[child] < *item)) {
98 this->data[gap] = this->data[child];
124 if (!(*item < *this->
data[parent])) {
128 this->data[gap] = this->data[parent];
136 inline void CheckConsistency()
138 assert(this->items == this->data.size() - 1);
139 for (
size_t child = 2; child <= this->
items; child++) {
140 size_t parent = child / 2;
141 assert(!(*this->data[child] < *this->data[parent]));
164 return this->items == 0;
175 return this->data[1];
187 return this->data[1 + this->
items];
198 this->data.emplace_back();
199 size_t gap = this->
HeapifyUp(++items, new_item);
200 this->data[gap] = new_item;
214 T *first = this->
Begin();
218 T *last = this->
End();
221 if (!this->
IsEmpty()) this->data[gap] = last;
222 this->data.pop_back();
235 if (index < this->
items) {
240 T *last = this->
End();
242 size_t gap = this->
HeapifyUp(index, last);
245 if (!this->
IsEmpty()) this->data[gap] = last;
247 assert(index == this->items);
250 this->data.pop_back();
265 auto it = std::find(this->data.begin(), this->data.end(), &item);
266 return it == this->data.end() ? 0 : std::distance(this->data.begin(), it);
276 this->data.resize(1);