|
| int | 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. More...
|
| |
| void | heapdown () |
| |
| void | heapup (int idx) |
| |
| | BinaryHeapSimple (int size) |
| | Construtor, giving initial array size. More...
|
| |
| void | clear () |
| | empties the heap [O(1)] More...
|
| |
| bool | empty () const |
| | Returns true if the heap is empty. More...
|
| |
| X | extractMin () |
| | Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)]. More...
|
| |
| 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)]. More...
|
| |
| void | insert (X &x) |
| | Adds an element to the heap [Same as push(), O(log n)]. More...
|
| |
| const X & | operator[] (int idx) const |
| | obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays) More...
|
| |
| X | pop () |
| | Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)]. More...
|
| |
| void | push (X &x) |
| | Adds an element to the heap [Same as insert(), O(log n)]. More...
|
| |
| int | size () const |
| | Returns the number of elements in the heap. More...
|
| |
| 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)]. More...
|
| |
template<class X, class INDEX = int>
class ogdf::Top10Heap< X, INDEX >
A variant of BinaryHeapSimple which always holds only the 10 elements with the highest keys.
It assumes that the data-elements are themselves comparable, i.e., the compare-function of the items implicitly defines the keys.
If your intended datastructure do not directly offer a compare function, but you have certain key-values (scores, etc.), you may want to use the convenience-class Prioritized < Priority,X > to bind both together and use within BinaryHeapSimple.
Definition at line 148 of file MinHeap.h.
template<class X , class INDEX = int>
obtain const references to the element at index idx
The smallest array index is 0, as for traditional C-arrays. Useful, e.g., when iterating through the final heap elements.
Definition at line 231 of file MinHeap.h.
template<class X , class INDEX = int>
Tries to push the element x onto the heap (and may return a removed element as out).
If the heap is not yet completely filled, the pushed element is accepted and added to the heap. The function returns PushResult::Accepted, and the out parameter is not touched.
If the heap is filled and the key of the pushed element is too small to be accepted (i.e. the heap is filled with all larger elements), then the element if rejected: The funtion returns PushResult::Rejected, and the out parameter is set to x.
If the heap is filled and the key of the pushed element is large enough to belong to the top elements, the element is accepted and the currently smallest element in the heap is removed from the heap. The function returns PushResult::Swapped and sets the out parameter to the element removed from the heap.
You may want to use the convenience funtions successful and returnedSomething on the return-value if you are only interested certain aspects of the push.
Definition at line 190 of file MinHeap.h.
Inheritance diagram for ogdf::Top10Heap< X, INDEX >:
