Public Member Functions
| ||BinaryHeap2 (int startSize=128)|
| ||Creates a binary heap. |
|virtual ||~BinaryHeap2 ()|
|int ||capacity () const |
| ||Returns the current size. |
|void ||clear ()|
| ||Reinitializes the data structure. |
|virtual void ||decreaseKey (int index, key priority)|
| ||Decreases priority of an object that is addressed by index. |
|int ||empty () const |
| ||Returns true iff the heap is empty. |
|HeapObject ||extractMin ()|
| ||Returns minimum priority element and removes it from the heap. |
|key ||getPriority (int index) const |
|void ||insert (HeapObject &obj, key &p, int *keyUpdate=0)|
| ||Inserts a new element obj with priority p and pointer for index update. |
|virtual void ||makeHeap ()|
| ||Obtains heap property, only needed if the elements are not inserted by insert method. |
|HeapObject ||minRet () const |
| ||Returns minimum priority element. |
|const BinaryHeap2 & ||operator= (const BinaryHeap2< key, HeapObject > &rhs)|
| ||Assignment operator. |
|int ||size () const |
| ||Returns the number of stored elements. |
| ||HeapBase ()|
| ||Constructor. |
|virtual ||~HeapBase ()|
|virtual void ||decreaseKey ()|
| ||update the data structure by decreasing the key of an object |
|virtual void ||insert (HeapObject, key)|
| ||insert a new element with priority key |
|HeapObject ||minRet ()|
template<class key, class HeapObject>
class ogdf::BinaryHeap2< key, HeapObject >
Min-heap priority queue realized by a data array.
Heaps store objects that are weighted with costs; the minimal cost object is accessible over member function minRet() and extracted by extractMin().
The class uses two template parameters:
- key is the key type.
- HeapElement is the type of the elements that are stored.
HeapObjects can be all types with copy constructor, as copies of inserted elements are created; key should be of a type with compare operators. We only allow integer as index/size type; the array index starts with 1.
To allow direct access to the underlying array structure in order to minimize decreaseKey() runningtime, a pointer to an integer storage can be provided as input() parameter that will be kept updated with the index position during heap operations.
The worst case running times of the methods is given by the following table, where n is the current number of elements.
Definition at line 105 of file BinaryHeap2.h.