ogdf::MinHeap< X, INDEX > Class Template Reference
Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap).
More...
#include <MinHeap.h>
List of all members.
|
Public Member Functions |
| | MinHeap (INDEX size) |
| | Construtor, giving initial array size.
|
| bool | empty () const |
| | Returns true if the heap is empty.
|
| INDEX | size () const |
| | Returns the number of elements in the heap.
|
| void | clear () |
| | empties the heap
|
| const X & | top () const |
| | Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [O(1)].
|
| void | push (X &x) |
| | Adds an element to the heap [O(log n)].
|
| X | pop () |
| | Returns the top (i.e., smallest) element and removed it from the heap [O(log n)].
|
| const X & | operator[] (INDEX idx) const |
| | obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays)
|
Protected Member Functions |
| INDEX | capacity () const |
| | Returns the current array-size of the heap, i.e., the number of elements which can be added before the next resize occurs.
|
| void | heapup (INDEX idx) |
| void | heapdown () |
Private Attributes |
| Array< X, INDEX > | data |
| INDEX | num |
Detailed Description
template<class X, class INDEX = int>
class ogdf::MinHeap< X, INDEX >
Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap).
It assumes that the data-elements are themselves comparable, i.e., the compare-function of the items implicitly defines the keys. Hence this datastructure allows no key-changing operations (decreaseKey, etc.).
The heap grows (using doubling) dynamically, if there are more elements added. Furthermore, MinHeap allows to be directly indexed using traditional array-syntax, e.g., for iterating over all its elements.
If your intended datastructure do not dorectly offer a compare function, but you have certain key-values (scores, etc.), you may want to use the convenience-class Valued < Score,X > to bind both together and use within MinHeap.
Definition at line 110 of file MinHeap.h.
Constructor & Destructor Documentation
template<class X, class INDEX = int>
Construtor, giving initial array size.
Definition at line 116 of file MinHeap.h.
Member Function Documentation
template<class X, class INDEX = int>
template<class X, class INDEX = int>
template<class X, class INDEX = int>
template<class X, class INDEX = int>
Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [O(1)].
Definition at line 127 of file MinHeap.h.
template<class X, class INDEX = int>
Adds an element to the heap [O(log n)].
Definition at line 132 of file MinHeap.h.
template<class X, class INDEX = int>
Returns the top (i.e., smallest) element and removed it from the heap [O(log n)].
Definition at line 141 of file MinHeap.h.
template<class X, class INDEX = int>
| const X& ogdf::MinHeap< X, INDEX >::operator[] |
( |
INDEX |
idx |
) |
const [inline] |
obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays)
Reimplemented in ogdf::Top10Heap< X, INDEX >.
Definition at line 148 of file MinHeap.h.
template<class X, class INDEX = int>
| INDEX ogdf::MinHeap< X, INDEX >::capacity |
( |
|
) |
const [inline, protected] |
Returns the current array-size of the heap, i.e., the number of elements which can be added before the next resize occurs.
Reimplemented in ogdf::Top10Heap< X, INDEX >.
Definition at line 155 of file MinHeap.h.
template<class X, class INDEX = int>
| void ogdf::MinHeap< X, INDEX >::heapup |
( |
INDEX |
idx |
) |
[inline, protected] |
template<class X, class INDEX = int>
Member Data Documentation
template<class X, class INDEX = int>
template<class X, class INDEX = int>
The documentation for this class was generated from the following file:
© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.
Generated on Thu Nov 22 19:40:08 2007 by doxygen 1.5.4.
