10 #ifndef BINARYHEAP_HPP 11 #define BINARYHEAP_HPP 13 #include "../core/alloc_func.hpp" 16 #define BINARYHEAP_CHECK 0 20 #define CHECK_CONSISTY() this->CheckConsistency() 23 #define CHECK_CONSISTY() ; 66 this->data = MallocT<T *>(max_items + 1);
94 while (child <= this->items) {
96 if (child < this->items && *this->data[child + 1] < *this->data[child]) {
100 if (!(*this->data[child] < *item)) {
105 this->data[gap] = this->data[child];
131 if (!(*item < *this->data[parent])) {
135 this->data[gap] = this->data[parent];
143 inline void CheckConsistency()
145 for (uint child = 2; child <= this->
items; child++) {
146 uint parent = child / 2;
147 assert(!(*this->data[child] < *this->data[parent]));
170 return this->items == 0;
180 return this->items >= this->
capacity;
191 return this->data[1];
203 return this->data[1 + this->
items];
214 assert(this->capacity < UINT_MAX / 2);
217 this->data = ReallocT<T*>(this->
data, this->capacity + 1);
221 uint gap = this->
HeapifyUp(++items, new_item);
222 this->data[gap] = new_item;
236 T *first = this->
Begin();
240 T *last = this->
End();
243 if (!this->
IsEmpty()) this->data[gap] = last;
256 if (index < this->items) {
261 T *last = this->
End();
266 if (!this->
IsEmpty()) this->data[gap] = last;
268 assert(index == this->items);
285 for (T **ppI = this->data + 1, **ppLast = ppI + this->items; ppI <= ppLast; ppI++) {
287 return ppI - this->
data;
uint Length() const
Get the number of items stored in the priority queue.
T * Begin()
Get the smallest item in the binary tree.
uint HeapifyUp(uint gap, T *item)
Get position for fixing a gap (upwards).
uint capacity
Maximum number of items the heap can hold.
uint items
Number of items in the heap.
bool IsEmpty() const
Test if the priority queue is empty.
CBinaryHeapT(uint max_items)
Create a binary heap.
bool IsFull() const
Test if the priority queue is full.
uint HeapifyDown(uint gap, T *item)
Get position for fixing a gap (downwards).
void Clear()
Make the priority queue empty.
#define CHECK_CONSISTY()
Don't check for consistency.
uint FindIndex(const T &item) const
Search for an item in the priority queue.
T * Shift()
Remove and return the smallest (and also first) item from the priority queue.
Binary Heap as C++ template.
T ** data
The pointer to the heap item pointers.
void Include(T *new_item)
Insert new item into the priority queue, maintaining heap order.
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
void Remove(uint index)
Remove item at given index from the priority queue.
T * End()
Get the LAST item in the binary tree.