Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap). More...
#include <ogdf/basic/MinHeap.h>
Public Member Functions  
BinaryHeapSimple (INDEX 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[] (INDEX idx) const 
obtain const references to the element at index idx (the smallest array index is 0, as for traditional Carrays) 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...  
INDEX  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...  
Protected Member Functions  
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. More...  
void  heapdown () 
void  heapup (INDEX idx) 
Private Attributes  
Array< X, INDEX >  data 
INDEX  num 
Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap).
It assumes that the dataelements are themselves comparable, i.e., the comparefunction of the items implicitly defines the keys. Hence this datastructure allows no keychanging operations (decreaseKey, etc.).
The heap grows (using doubling) dynamically, if there are more elements added. Furthermore, BinaryHeapSimple allows to be directly indexed using traditional arraysyntax, e.g., for iterating over all its elements.
If your intended datastructure does not offer a (suitable) compare function, but you have certain keyvalues (scores, etc.), you may want to use the convenienceclass Prioritized < Score,X > to bind both together and use within BinaryHeapSimple.

inlineexplicit 

inlineprotected 

inline 

inline 

inline 

inline 

inlineprotected 

inlineprotected 

inline 

inline 

inline 
Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)].

inline 

inline 

inline 

private 

private 