A variant of BinaryHeapSimple which always holds only the 10 elements with the highest keys. More...
#include <ogdf/basic/MinHeap.h>
Public Types  
enum class  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.  
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.  
Static Public Member Functions  
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.  
Additional Inherited Members  
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 BinaryHeapSimple which always holds only the 10 elements with the highest keys.
It assumes that the dataelements are themselves comparable, i.e., the comparefunction of the items implicitly defines the keys.
If your intended datastructure do not directly offer a compare function, but you have certain keyvalues (scores, etc.), you may want to use the convenienceclass Prioritized < Priority,X > to bind both together and use within BinaryHeapSimple.
The type for results of a Top10Heap::push operation.
Enumerator  

Accepted  
Rejected  
Swapped 

inline 

inline 
Alternative name for pushBlind().

inline 

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 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 returnvalue if you are only interested certain aspects of the push.
Simple (and slightly faster) variant of Top10Heap::push.
The behavior is the identical to Top10Heap::push, but there is nothing reported to the outside

inlinestatic 

inlinestatic 