|
|||
|
|
|
|||
|
|
Binary heaps. More...
#include <ogdf/lib/abacus/bheap.h>
Public Member Functions | |
| AbaBHeap (const ArrayBuffer< Type > &elems, const ArrayBuffer< Key > &keys) | |
| A constructor with initialization. More... | |
| AbaBHeap (int size) | |
| A constructor. More... | |
| void | check () const |
| Throws an exception if the heap properties are violated. More... | |
| void | clear () |
| Empties the heap. More... | |
| bool | empty () const |
| Return true if there are no elements in the heap, false otherwise. More... | |
| Type | extractMin () |
| Accesses and removes the minimum element from the heap. More... | |
| Type | getMin () const |
| Returns the minimum element of the heap. More... | |
| Key | getMinKey () const |
| Returns the key of the minimum element of the heap. More... | |
| void | insert (Type elem, Key key) |
| Inserts an item with a key into the heap. More... | |
| int | number () const |
| Returns the number of elements in the heap. More... | |
| void | realloc (int newSize) |
| Changes the size of the heap. More... | |
| int | size () const |
| Returns the maximal number of elements which can be stored in the heap. More... | |
Private Member Functions | |
| int | father (int i) const |
| Returns the index of the father of element i. More... | |
| void | heapify (int i) |
| Is the central function to maintain the heap property. More... | |
| int | leftSon (int i) const |
| Returns the index of the left son of node i. More... | |
| int | rightSon (int i) const |
| Returns the index of the right son of node i. More... | |
Private Attributes | |
| Array< Type > | heap_ |
| Array< Key > | keys_ |
| int | n_ |
Friends | |
| std::ostream & | operator<< (std::ostream &out, const AbaBHeap< Type, Key > &heap) |
| The output operator. More... | |
Binary heaps.
A heap is the representation of a binary tree by an array a.
The root of the tree is associated with a[0]. If a node corresponds to a[i], then its left son corresponds to a[2*i+1] and its right son to a[2*i+2]. This implicit binary tree is completely filled except possibly its highest level. Every item in the heap has to fulfil the heap property, i.e., its key has to be less than or equal than the keys of both sons.
This template class implements a heap with a fixed maximal size, however a reallocation can be performed if required.
The operations insert(), extractMin() require O(log n) running time if n elements are contained in the heap. The operation getMin() can even be executed in constant time. A heap can also be constructed from an ArrayBuffer of n elements which requires a running time of O(n) only.
The order of the elements in the heap is given by keys which are inserted together with each element of the heap. The class Key must be from an ordered type. Given two objects k1 and k2 of type Key then k1 has higher priority if the expression k1 < k2 holds.
|
explicit |
A constructor.
| size | The maximal number of elements which can be stored. |
| abacus::AbaBHeap< Type, Key >::AbaBHeap | ( | const ArrayBuffer< Type > & | elems, |
| const ArrayBuffer< Key > & | keys | ||
| ) |
A constructor with initialization.
The heap is initialized from an ArrayBuffer of elements and a corresponding ArrayBuffer of keys. The running time is O(n) for n elements.
| elems | A ArrayBuffer wich contains the elements. |
| keys | A ArrayBuffer wich contains the keys. |
| void abacus::AbaBHeap< Type, Key >::check | ( | ) | const |
Throws an exception if the heap properties are violated.
This function is used for debugging this class.
| void abacus::AbaBHeap< Type, Key >::clear | ( | ) |
Empties the heap.
| bool abacus::AbaBHeap< Type, Key >::empty | ( | ) | const |
Return true if there are no elements in the heap, false otherwise.
| Type abacus::AbaBHeap< Type, Key >::extractMin | ( | ) |
Accesses and removes the minimum element from the heap.
The minimum element is stored in the root of the tree, i.e., in heap_[0]. If the heap does not become empty by removing the minimal element, we move the last element stored in heap_ to the root (heap_[0]). Whereas this operation can destroy the heap property, the two subtrees rooted at nodes 1 and 2 still satisfy the heap property. Hence calling heapify(0) will restore the overall heap property.
|
private |
Returns the index of the father of element i.
| Type abacus::AbaBHeap< Type, Key >::getMin | ( | ) | const |
Returns the minimum element of the heap.
This operation must not be performed if the heap is empty. Since the heap property holds the element having minimal key is always stored in heap_[0].
| Key abacus::AbaBHeap< Type, Key >::getMinKey | ( | ) | const |
Returns the key of the minimum element of the heap.
This operation must not be performed if the heap is empty. Since the heap property holds the element having minimal key is always stored in heap_[0] and its key in key_[0].
|
private |
Is the central function to maintain the heap property.
The function assumes that the two trees rooted at left(i) and right(i) fulfil already the heap property and restores the heap property of the (sub-) tree rooted at i.
| void abacus::AbaBHeap< Type, Key >::insert | ( | Type | elem, |
| Key | key | ||
| ) |
Inserts an item with a key into the heap.
It is a fatal error to perform this operation if the heap is full.
| elem | The element being inserted into the heap. |
| key | The key of this element. |
|
private |
Returns the index of the left son of node i.
| int abacus::AbaBHeap< Type, Key >::number | ( | ) | const |
Returns the number of elements in the heap.
| void abacus::AbaBHeap< Type, Key >::realloc | ( | int | newSize | ) |
Changes the size of the heap.
| newSize | The new maximal number of elements in the heap. |
|
private |
Returns the index of the right son of node i.
| int abacus::AbaBHeap< Type, Key >::size | ( | ) | const |
Returns the maximal number of elements which can be stored in the heap.
|
friend |
The output operator.
Writes the elements of the heap together with their keys on an output stream.
| out | The output stream. |
| heap | The heap being output. |
|
private |
|
private |
|
private |
