|
|||
|
|
|
|||
|
|
#include <MinHeap.h>
Public Types | |
| enum | PushResult { Accepted, Rejected, Swapped } |
| The type for results of a Top10Heap::push operation. More... | |
Public Member Functions | |
| Top10Heap () | |
| Constructor generating a heap which holds the 10 elements with highest value ever added to the heap. | |
| Top10Heap (INDEX size) | |
| Constructor generating a heap which holds the size elements with highest value ever added to the heap. | |
| bool | empty () const |
| Returns true if the heap contains no elements. | |
| bool | full () const |
| Returns true if the heap is completely filled (i.e. the next push operation will return something). | |
| INDEX | size () const |
| Returns the number of elements in the heap. | |
| INDEX | capacity () const |
| Returns the size of the heap specified when constructing: this is the number of top elements stored. | |
| void | clear () |
| empties the heap | |
| PushResult | push (X &x, X &out) |
| Tries to push the element x onto the heap (and may return a removed element as out). | |
| void | pushBlind (X &x) |
| Simple (and slightly faster) variant of Top10Heap::push. | |
| const X & | operator[] (INDEX idx) const |
| obtain const references to the element at index idx | |
Static Public Member Functions | |
| static bool | successful (PushResult r) |
| Convenience function: Returns true if the PushResults states that the newly pushed element is new in the heap. | |
| static bool | returnedSomething (PushResult r) |
| Convenience function: Returns true if the PushResults states that push caused an element to be not/no-longer in the heap. | |
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 dorectly offer a compare function, but you have certain key-values (scores, etc.), you may want to use the convenience-class Valued < Score,X > to bind both together and use within MinHeap.
Definition at line 191 of file MinHeap.h.
| enum ogdf::Top10Heap::PushResult |
The type for results of a Top10Heap::push operation.
| ogdf::Top10Heap< X, INDEX >::Top10Heap | ( | ) | [inline] |
| ogdf::Top10Heap< X, INDEX >::Top10Heap | ( | INDEX | size | ) | [inline] |
| static bool ogdf::Top10Heap< X, INDEX >::successful | ( | PushResult | r | ) | [inline, static] |
| static bool ogdf::Top10Heap< X, INDEX >::returnedSomething | ( | PushResult | r | ) | [inline, static] |
| bool ogdf::Top10Heap< X, INDEX >::empty | ( | ) | const [inline] |
| bool ogdf::Top10Heap< X, INDEX >::full | ( | ) | const [inline] |
| INDEX ogdf::Top10Heap< X, INDEX >::size | ( | ) | const [inline] |
| INDEX ogdf::Top10Heap< X, INDEX >::capacity | ( | ) | const [inline] |
Returns the size of the heap specified when constructing: this is the number of top elements stored.
Reimplemented from ogdf::MinHeap< X, INDEX >.
| void ogdf::Top10Heap< X, INDEX >::clear | ( | ) | [inline] |
| PushResult ogdf::Top10Heap< X, INDEX >::push | ( | X & | x, | |
| X & | out | |||
| ) | [inline] |
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 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 Rejected, and the out parameter is set to .
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 Swapped and sets the 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.
| void ogdf::Top10Heap< X, INDEX >::pushBlind | ( | X & | x | ) | [inline] |
Simple (and slightly faster) variant of Top10Heap::push.
The behavior is the identical to Top10Heap::push, but there is nothing reported to the outside
| const X& ogdf::Top10Heap< X, INDEX >::operator[] | ( | INDEX | idx | ) | const [inline] |
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.
Reimplemented from ogdf::MinHeap< X, INDEX >.
