Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap).
More...
Public Member Functions |
| | BinaryHeapSimple (INDEX size) |
| | Construtor, giving initial array size.
|
| bool | empty () const |
| | Returns true if the heap is empty.
|
| INDEX | size () const |
| | Returns the number of elements in the heap.
|
| void | clear () |
| | empties the heap [O(1)]
|
| const X & | top () const |
| | Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as getMin(), O(1)].
|
| const X & | getMin () const |
| | Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as top(), O(1)].
|
| void | push (X &x) |
| | Adds an element to the heap [Same as insert(), O(log n)].
|
| void | insert (X &x) |
| | Adds an element to the heap [Same as push(), O(log n)].
|
| X | pop () |
| | Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)].
|
| X | extractMin () |
| | Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)].
|
| const X & | operator[] (INDEX idx) const |
| | obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays)
|
Protected Member Functions |
| INDEX | capacity () const |
| | Returns the current array-size of the heap, i.e., the number of elements which can be added before the next resize occurs.
|
| void | heapup (INDEX idx) |
| void | heapdown () |
Private Attributes |
| Array< X, INDEX > | data |
| INDEX | num |
template<class X, class INDEX = int>
class ogdf::BinaryHeapSimple< X, INDEX >
Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap).
It assumes that the data-elements are themselves comparable, i.e., the compare-function of the items implicitly defines the keys. Hence this datastructure allows no key-changing operations (decreaseKey, etc.).
The heap grows (using doubling) dynamically, if there are more elements added. Furthermore, BinaryHeapSimple allows to be directly indexed using traditional array-syntax, e.g., for iterating over all its elements.
If your intended datastructure does not offer a (suitable) compare function, but you have certain key-values (scores, etc.), you may want to use the convenience-class Prioritized < Score,X > to bind both together and use within BinaryHeapSimple.
Definition at line 102 of file MinHeap.h.
