Public Member Functions |
| | DeletingTop10Heap (int size) |
| | Construct a DeletingTop10Heap of given maximal capacity.
|
| void | insertAndDelete (X *x, Priority p) |
| | Alternative name for pushAndDelete().
|
| void | insertAndDeleteNoRedundancy (X *x, Priority p) |
| | Alternative name for pushAndKillNoRedundancy().
|
| void | pushAndDelete (X *x, Priority p) |
| | Inserts the element x into the heap with priority val and deletes the element with smallest priority if the heap is full.
|
| void | pushAndDeleteNoRedundancy (X *x, Priority p) |
| | Analogous to pushandDelete(), but furthermore rejects (and deletes) an element if an equal element is already in the heap.
|
| | 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.
|
| 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
|
| 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)
|
| PushResult | insert (Prioritized< X *, Priority > &x, Prioritized< X *, Priority > &out) |
| | Alternative name for push().
|
| void | insertBlind (Prioritized< X *, Priority > &x, Prioritized< X *, Priority > &out) |
| | Alternative name for pushBlind().
|
const Prioritized< X
*, Priority > & | operator[] (INDEX idx) const |
| | obtain const references to the element at index idx
|
| PushResult | push (Prioritized< X *, Priority > &x, Prioritized< X *, Priority > &out) |
| | Tries to push the element x onto the heap (and may return a removed element as out).
|
| void | pushBlind (Prioritized< X *, Priority > &x) |
| | Simple (and slightly faster) variant of Top10Heap::push.
|
| INDEX | size () const |
| | Returns the number of elements in the heap.
|
template<class X, class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
class ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >
A variant of Top10Heap which deletes the elements that get rejected from the heap.
The datastructure of course requires the stored data-elements to be pointers (in order to be deletable when rejected). Hence the template parameter only specifies the data-type, without stating axplicitly that we considere pointers to the structure.
The datastructure also allows for non-duplicate insertions, i.e., a new element can be rejected if it is already in the heap. Note that only the compare function has to work
Definition at line 295 of file MinHeap.h.
template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
Inserts the element x into the heap with priority val and deletes the element with smallest priority if the heap is full.
Like the Top10Heap, this function pushes the element x onto the heap with priority val, and extracts the element with smallest priority if the heap was already full. In contrast to the Top10Heap, this element which leaves the heap (or x itself if its priority was below all the priorities in the heap) gets deleted, i.e., removed from memory.
Definition at line 305 of file MinHeap.h.
template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
| void ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >::pushAndDeleteNoRedundancy |
( |
X * |
x, |
|
|
Priority |
p |
|
) |
| |
|
inline |
Analogous to pushandDelete(), but furthermore rejects (and deletes) an element if an equal element is already in the heap.
This function takes linear time in the worst case, and uses the compare function of the specified COMP template paremeter class, which can be any function returning true if two objects should be considered equal, and false otherwise.
Definition at line 320 of file MinHeap.h.
Inheritance diagram for ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >:
