A variant of Top10Heap which deletes the elements that get rejected from the heap. More...
#include <ogdf/basic/MinHeap.h>
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 p 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.  
Public Member Functions inherited from ogdf::Top10Heap< X, INDEX >  
Top10Heap ()  
Constructor generating a heap which holds the 10 elements with highest value ever added to the heap.  
bool  full () const 
Returns true if the heap is completely filled (i.e. the next push operation will return something)  
PushResult  insert (X &x, X &out) 
Alternative name for push().  
void  insertBlind (X &x) 
Alternative name for pushBlind().  
const X &  operator[] (INDEX idx) const 
obtain const references to the element at index idx  
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.  
Additional Inherited Members  
Public Types inherited from ogdf::Top10Heap< X, INDEX >  
enum class  PushResult { Accepted , Rejected , Swapped } 
The type for results of a Top10Heap::push operation. More...  
Static Public Member Functions inherited from ogdf::Top10Heap< X, INDEX >  
static bool  returnedSomething (PushResult r) 
Convenience function: Returns true if the PushResults states that push caused an element to be not/nolonger in the heap.  
static bool  successful (PushResult r) 
Convenience function: Returns true if the PushResults states that the newly pushed element is new in the heap.  
Protected Member Functions inherited from ogdf::BinaryHeapSimple< X, INDEX >  
INDEX  capacity () const 
Returns the current arraysize of the heap, i.e., the number of elements which can be added before the next resize occurs.  
void  heapdown () 
void  heapup (INDEX idx) 
BinaryHeapSimple (INDEX size)  
Construtor, giving initial array size.  
void  clear () 
empties the heap [O(1)]  
bool  empty () const 
Returns true if the heap is empty.  
X  extractMin () 
Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)].  
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  insert (X &x) 
Adds an element to the heap [Same as push(), 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 Carrays)  
X  pop () 
Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)].  
void  push (X &x) 
Adds an element to the heap [Same as insert(), O(log n)].  
INDEX  size () const 
Returns the number of elements in the heap.  
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)].  
A variant of Top10Heap which deletes the elements that get rejected from the heap.
The datastructure of course requires the stored dataelements to be pointers (in order to be deletable when rejected). Hence the template parameter only specifies the datatype, without stating axplicitly that we considere pointers to the structure.
The datastructure also allows for nonduplicate 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

inlineexplicit 
Construct a DeletingTop10Heap of given maximal capacity.

inline 
Alternative name for pushAndDelete().

inline 
Alternative name for pushAndKillNoRedundancy().

inline 
Inserts the element x
into the heap with priority p
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 p
, 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.

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.