|
|||
|
|
|
|||
|
|
Min-heap priority queue realized by a data array. More...
#include <ogdf/basic/BinaryHeap2.h>
Classes | |
| struct | HeapEntry |
Public Member Functions | |
| BinaryHeap2 (int startSize=128) | |
| Creates a binary heap. | |
| virtual | ~BinaryHeap2 () |
| const BinaryHeap2 & | operator= (const BinaryHeap2< key, HeapObject > &rhs) |
| Assignment operator. | |
| 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 | extractMin () |
| Returns minimum priority element and removes it from the heap. | |
| virtual void | decreaseKey (int index, key priority) |
| Decreases priority of an object that is addressed by index. | |
| HeapObject | minRet () const |
| Returns minimum priority element. | |
| key | getPriority (int index) const |
| int | capacity () const |
| Returns the current size. | |
| int | size () const |
| Returns the number of stored elements. | |
| int | empty () const |
| Returns true iff the heap is empty. | |
| void | clear () |
| Reinitializes the data structure. | |
Protected Member Functions | |
| void | siftUp (int pos) |
| Establishes heap property by moving element up in heap if necessary. | |
| void | siftDown (int pos) |
| Establishes heap property by moving element down in heap if necessary. | |
| int | parentIndex (int num) |
| Array index of parent node. | |
| int | leftChildIndex (int num) |
| Array index of left child. | |
| int | rightChildIndex (int num) |
| Array index of right child. | |
| bool | hasLeft (int num) |
| Returns true if left child exists. | |
| bool | hasRight (int num) |
| Returns true if right child exists. | |
| int | arrayBound (int arraySize) |
| int | higherArrayBound (int arraySize) |
| int | higherArraySize (int arraySize) |
| int | lowerArrayBound (int arraySize) |
| int | lowerArraySize (int arraySize) |
| void | init (int initSize) |
Private Attributes | |
| HeapEntry * | m_heapArray |
| int | m_arraySize |
| int | m_startSize |
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:
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.
| method | worst-case | amortized |
|---|---|---|
| extractMin() | O(n) | O(lg(n)) |
| siftDown() | O(lg(n)) | |
| siftUp() | O(lg(n)) | |
| minRet() | O(1) | |
| insert() | O(n) | O(lg(n)) |
Definition at line 104 of file BinaryHeap2.h.
| ogdf::BinaryHeap2< key, HeapObject >::BinaryHeap2 | ( | int | startSize = 128 | ) |
Creates a binary heap.
Definition at line 297 of file BinaryHeap2.h.
| virtual ogdf::BinaryHeap2< key, HeapObject >::~BinaryHeap2 | ( | ) | [inline, virtual] |
Definition at line 114 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::arrayBound | ( | int | arraySize | ) | [inline, protected] |
Definition at line 219 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::capacity | ( | ) | const [inline] |
Returns the current size.
Definition at line 157 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::clear | ( | ) |
Reinitializes the data structure.
Deletes the array and reallocates it with size that was passed at construction time.
Definition at line 316 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::decreaseKey | ( | int | index, |
| key | priority | ||
| ) | [virtual] |
Decreases priority of an object that is addressed by index.
Definition at line 419 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::empty | ( | ) | const [inline] |
Returns true iff the heap is empty.
Reimplemented from ogdf::HeapBase< key, HeapObject >.
Definition at line 163 of file BinaryHeap2.h.
| HeapObject ogdf::BinaryHeap2< key, HeapObject >::extractMin | ( | ) |
Returns minimum priority element and removes it from the heap.
Definition at line 433 of file BinaryHeap2.h.
| key ogdf::BinaryHeap2< key, HeapObject >::getPriority | ( | int | index | ) | const [inline] |
Definition at line 150 of file BinaryHeap2.h.
| bool ogdf::BinaryHeap2< key, HeapObject >::hasLeft | ( | int | num | ) | [inline, protected] |
Returns true if left child exists.
Definition at line 204 of file BinaryHeap2.h.
| bool ogdf::BinaryHeap2< key, HeapObject >::hasRight | ( | int | num | ) | [inline, protected] |
Returns true if right child exists.
Definition at line 211 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::higherArrayBound | ( | int | arraySize | ) | [inline, protected] |
Definition at line 220 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::higherArraySize | ( | int | arraySize | ) | [inline, protected] |
Definition at line 221 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::init | ( | int | initSize | ) | [protected] |
Definition at line 304 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::insert | ( | HeapObject & | obj, |
| key & | p, | ||
| int * | keyUpdate = 0 |
||
| ) |
Inserts a new element obj with priority p and pointer for index update.
Definition at line 469 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::leftChildIndex | ( | int | num | ) | [inline, protected] |
Array index of left child.
Definition at line 190 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::lowerArrayBound | ( | int | arraySize | ) | [inline, protected] |
Definition at line 222 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::lowerArraySize | ( | int | arraySize | ) | [inline, protected] |
Definition at line 223 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::makeHeap | ( | ) | [virtual] |
Obtains heap property, only needed if the elements are not inserted by insert method.
Implements ogdf::HeapBase< key, HeapObject >.
Definition at line 410 of file BinaryHeap2.h.
| HeapObject ogdf::BinaryHeap2< key, HeapObject >::minRet | ( | ) | const [inline] |
Returns minimum priority element.
Definition at line 148 of file BinaryHeap2.h.
| const BinaryHeap2< key, HeapObject > & ogdf::BinaryHeap2< key, HeapObject >::operator= | ( | const BinaryHeap2< key, HeapObject > & | rhs | ) |
Assignment operator.
Definition at line 495 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::parentIndex | ( | int | num | ) | [inline, protected] |
Array index of parent node.
Definition at line 183 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::rightChildIndex | ( | int | num | ) | [inline, protected] |
Array index of right child.
Definition at line 197 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::siftDown | ( | int | pos | ) | [protected] |
Establishes heap property by moving element down in heap if necessary.
Definition at line 360 of file BinaryHeap2.h.
| void ogdf::BinaryHeap2< key, HeapObject >::siftUp | ( | int | pos | ) | [protected] |
Establishes heap property by moving element up in heap if necessary.
Definition at line 328 of file BinaryHeap2.h.
| int ogdf::BinaryHeap2< key, HeapObject >::size | ( | ) | const [inline] |
Returns the number of stored elements.
Reimplemented from ogdf::HeapBase< key, HeapObject >.
Definition at line 160 of file BinaryHeap2.h.
int ogdf::BinaryHeap2< key, HeapObject >::m_arraySize [private] |
Definition at line 276 of file BinaryHeap2.h.
HeapEntry* ogdf::BinaryHeap2< key, HeapObject >::m_heapArray [private] |
Definition at line 271 of file BinaryHeap2.h.
int ogdf::BinaryHeap2< key, HeapObject >::m_startSize [private] |
Definition at line 278 of file BinaryHeap2.h.
