Go to the documentation of this file.
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 HeapifyUp(uint gap, T *item)
Get position for fixing a gap (upwards).
#define CHECK_CONSISTY()
Don't check for consistency.
uint items
Number of items in the heap.
T * Shift()
Remove and return the smallest (and also first) item from the priority queue.
uint capacity
Maximum number of items the heap can hold.
T ** data
The pointer to the heap item pointers.
bool IsEmpty() const
Test if the priority queue is empty.
Binary Heap as C++ template.
void Clear()
Make the priority queue empty.
CBinaryHeapT(uint max_items)
Create a binary heap.
uint HeapifyDown(uint gap, T *item)
Get position for fixing a gap (downwards).
bool IsFull() const
Test if the priority queue is full.
uint FindIndex(const T &item) const
Search for an item in the priority queue.
void Include(T *new_item)
Insert new item into the priority queue, maintaining heap order.
T * End()
Get the LAST item in the binary tree.
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.
uint Length() const
Get the number of items stored in the priority queue.
T * Begin()
Get the smallest item in the binary tree.