OpenTTD Source
20241111-master-gce64d5f5d9
|
Binary Heap as C++ template. More...
#include <binaryheap.hpp>
Public Member Functions | |
CBinaryHeapT (size_t initial_capacity) | |
Create a binary heap. More... | |
size_t | Length () const |
Get the number of items stored in the priority queue. More... | |
bool | IsEmpty () const |
Test if the priority queue is empty. More... | |
T * | Begin () |
Get the smallest item in the binary tree. More... | |
T * | End () |
Get the LAST item in the binary tree. More... | |
void | Include (T *new_item) |
Insert new item into the priority queue, maintaining heap order. More... | |
T * | Shift () |
Remove and return the smallest (and also first) item from the priority queue. More... | |
void | Remove (size_t index) |
Remove item at given index from the priority queue. More... | |
size_t | FindIndex (const T &item) const |
Search for an item in the priority queue. More... | |
void | Clear () |
Make the priority queue empty. More... | |
Protected Member Functions | |
size_t | HeapifyDown (size_t gap, T *item) |
Get position for fixing a gap (downwards). More... | |
size_t | HeapifyUp (size_t gap, T *item) |
Get position for fixing a gap (upwards). More... | |
Private Attributes | |
size_t | items = 0 |
Number of valid items in the heap. | |
std::vector< T * > | data |
The pointer to the heap item pointers. | |
Binary Heap as C++ template.
A carrier which keeps its items automatically holds the smallest item at the first position. The order of items is maintained by using a binary tree. The implementation is used for priority queues.
There are two major differences compared to std::priority_queue. First the std::priority_queue does not support indexing/removing elements in the middle of the heap/queue and second it has the biggest item first.
T | Type of the items stored in the binary heap |
Definition at line 53 of file binaryheap.hpp.
|
inlineexplicit |
Create a binary heap.
initial_capacity | The initial reserved capacity for the heap. |
Definition at line 63 of file binaryheap.hpp.
References CBinaryHeapT< T >::Clear().
|
inline |
Get the smallest item in the binary tree.
Definition at line 172 of file binaryheap.hpp.
Referenced by CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::GetBestOpenNode().
|
inline |
Make the priority queue empty.
All remaining items will remain untouched.
Definition at line 273 of file binaryheap.hpp.
References CHECK_CONSISTY.
Referenced by CBinaryHeapT< T >::CBinaryHeapT().
|
inline |
Get the LAST item in the binary tree.
Definition at line 185 of file binaryheap.hpp.
|
inline |
Search for an item in the priority queue.
Matching is done by comparing address of the item.
item | The reference to the item |
Definition at line 263 of file binaryheap.hpp.
Referenced by CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::PopOpenNode().
|
inlineprotected |
Get position for fixing a gap (downwards).
The gap is moved downwards in the binary tree until it is in order again.
gap | The position of the gap |
item | The proposed item for filling the gap |
Definition at line 79 of file binaryheap.hpp.
|
inlineprotected |
Get position for fixing a gap (upwards).
The gap is moved upwards in the binary tree until the is in order again.
gap | The position of the gap |
item | The proposed item for filling the gap |
Definition at line 115 of file binaryheap.hpp.
|
inline |
Insert new item into the priority queue, maintaining heap order.
new_item | The pointer to the new item |
Definition at line 195 of file binaryheap.hpp.
Referenced by CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::InsertOpenNode().
|
inline |
Test if the priority queue is empty.
Definition at line 162 of file binaryheap.hpp.
Referenced by CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::GetBestOpenNode(), and CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::PopBestOpenNode().
|
inline |
Get the number of items stored in the priority queue.
Definition at line 152 of file binaryheap.hpp.
References CBinaryHeapT< T >::items.
|
inline |
Remove item at given index from the priority queue.
index | The position of the item in the heap |
Definition at line 233 of file binaryheap.hpp.
References CBinaryHeapT< T >::items.
Referenced by CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::PopOpenNode().
|
inline |
Remove and return the smallest (and also first) item from the priority queue.
Definition at line 210 of file binaryheap.hpp.
Referenced by CNodeList_HashTableT< Titem_, Thash_bits_open_, Thash_bits_closed_ >::PopBestOpenNode().