|
|||
|
|
|
|||
|
|
#include <BinaryHeap.h>
Public Member Functions | |
| BinaryHeap (int startSize=128) | |
| Creates a binary heap. | |
| virtual | ~BinaryHeap () |
| const BinaryHeap & | operator= (const BinaryHeap< 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 |
Classes | |
| struct | HeapEntry |
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 112 of file BinaryHeap.h.
| ogdf::BinaryHeap< key, HeapObject >::BinaryHeap | ( | int | startSize = 128 |
) | [inline] |
| virtual ogdf::BinaryHeap< key, HeapObject >::~BinaryHeap | ( | ) | [inline, virtual] |
Definition at line 122 of file BinaryHeap.h.
| const BinaryHeap< key, HeapObject > & ogdf::BinaryHeap< key, HeapObject >::operator= | ( | const BinaryHeap< key, HeapObject > & | rhs | ) | [inline] |
| void ogdf::BinaryHeap< key, HeapObject >::insert | ( | HeapObject & | obj, | |
| key & | p, | |||
| int * | keyUpdate = 0 | |||
| ) | [inline] |
Inserts a new element obj with priority p and pointer for index update.
Definition at line 477 of file BinaryHeap.h.
| void ogdf::BinaryHeap< key, HeapObject >::makeHeap | ( | ) | [inline, virtual] |
Obtains heap property, only needed if the elements are not inserted by insert method.
Implements ogdf::HeapBase< key, HeapObject >.
Definition at line 418 of file BinaryHeap.h.
| HeapObject ogdf::BinaryHeap< key, HeapObject >::extractMin | ( | ) | [inline] |
Returns minimum priority element and removes it from the heap.
Definition at line 441 of file BinaryHeap.h.
| void ogdf::BinaryHeap< key, HeapObject >::decreaseKey | ( | int | index, | |
| key | priority | |||
| ) | [inline, virtual] |
Decreases priority of an object that is addressed by index.
Definition at line 427 of file BinaryHeap.h.
| HeapObject ogdf::BinaryHeap< key, HeapObject >::minRet | ( | ) | const [inline] |
| key ogdf::BinaryHeap< key, HeapObject >::getPriority | ( | int | index | ) | const [inline] |
Definition at line 158 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::capacity | ( | ) | const [inline] |
| int ogdf::BinaryHeap< key, HeapObject >::size | ( | ) | const [inline] |
Returns the number of stored elements.
Reimplemented from ogdf::HeapBase< key, HeapObject >.
Definition at line 168 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::empty | ( | ) | const [inline] |
Returns true iff the heap is empty.
Reimplemented from ogdf::HeapBase< key, HeapObject >.
Definition at line 171 of file BinaryHeap.h.
| void ogdf::BinaryHeap< key, HeapObject >::clear | ( | ) | [inline] |
Reinitializes the data structure.
Deletes the array and reallocates it with size that was passed at construction time.
Definition at line 324 of file BinaryHeap.h.
| void ogdf::BinaryHeap< key, HeapObject >::siftUp | ( | int | pos | ) | [inline, protected] |
Establishes heap property by moving element up in heap if necessary.
Definition at line 336 of file BinaryHeap.h.
| void ogdf::BinaryHeap< key, HeapObject >::siftDown | ( | int | pos | ) | [inline, protected] |
Establishes heap property by moving element down in heap if necessary.
Definition at line 368 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::parentIndex | ( | int | num | ) | [inline, protected] |
| int ogdf::BinaryHeap< key, HeapObject >::leftChildIndex | ( | int | num | ) | [inline, protected] |
| int ogdf::BinaryHeap< key, HeapObject >::rightChildIndex | ( | int | num | ) | [inline, protected] |
| bool ogdf::BinaryHeap< key, HeapObject >::hasLeft | ( | int | num | ) | [inline, protected] |
| bool ogdf::BinaryHeap< key, HeapObject >::hasRight | ( | int | num | ) | [inline, protected] |
| int ogdf::BinaryHeap< key, HeapObject >::arrayBound | ( | int | arraySize | ) | [inline, protected] |
Definition at line 227 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::higherArrayBound | ( | int | arraySize | ) | [inline, protected] |
Definition at line 228 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::higherArraySize | ( | int | arraySize | ) | [inline, protected] |
Definition at line 229 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::lowerArrayBound | ( | int | arraySize | ) | [inline, protected] |
Definition at line 230 of file BinaryHeap.h.
| int ogdf::BinaryHeap< key, HeapObject >::lowerArraySize | ( | int | arraySize | ) | [inline, protected] |
Definition at line 231 of file BinaryHeap.h.
| void ogdf::BinaryHeap< key, HeapObject >::init | ( | int | initSize | ) | [inline, protected] |
Definition at line 312 of file BinaryHeap.h.
HeapEntry* ogdf::BinaryHeap< key, HeapObject >::m_heapArray [private] |
Definition at line 279 of file BinaryHeap.h.
int ogdf::BinaryHeap< key, HeapObject >::m_arraySize [private] |
Definition at line 284 of file BinaryHeap.h.
int ogdf::BinaryHeap< key, HeapObject >::m_startSize [private] |
Definition at line 286 of file BinaryHeap.h.
