ogdf::BinaryHeapSimple< X, INDEX > Class Template Reference

Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap). More...

#include <ogdf/basic/MinHeap.h>

Inheritance diagram for ogdf::BinaryHeapSimple< X, INDEX >:

Public Member Functions
	BinaryHeapSimple (INDEX size)
	Construtor, giving initial array size.
void	clear ()
	empties the heap [O(1)]
bool	empty () const
	Returns true if the heap is empty.
X	extractMin ()
	Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)].
const X &	getMin () const
	Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as top(), O(1)].
void	insert (X &x)
	Adds an element to the heap [Same as push(), 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)
X	pop ()
	Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)].
void	push (X &x)
	Adds an element to the heap [Same as insert(), O(log n)].
INDEX	size () const
	Returns the number of elements in the heap.
const X &	top () const
	Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as getMin(), O(1)].

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	heapdown ()
void	heapup (INDEX idx)

Private Attributes
Array< X, INDEX >	data
INDEX	num

Detailed Description

template<class X, class INDEX = int>
class ogdf::BinaryHeapSimple< 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, BinaryHeapSimple allows to be directly indexed using traditional array-syntax, e.g., for iterating over all its elements.

If your intended datastructure does not offer a (suitable) compare function, but you have certain key-values (scores, etc.), you may want to use the convenience-class Prioritized < Score,X > to bind both together and use within BinaryHeapSimple.

Definition at line 54 of file MinHeap.h.

Constructor & Destructor Documentation

BinaryHeapSimple()

template<class X , class INDEX = int>

ogdf::BinaryHeapSimple< X, INDEX >::BinaryHeapSimple ( INDEX  size )

inlineexplicit

Construtor, giving initial array size.

Definition at line 61 of file MinHeap.h.

Member Function Documentation

capacity()

template<class X , class INDEX = int>

INDEX ogdf::BinaryHeapSimple< X, INDEX >::capacity ( ) const

inlineprotected

Returns the current array-size of the heap, i.e., the number of elements which can be added before the next resize occurs.

Definition at line 107 of file MinHeap.h.

clear()

template<class X , class INDEX = int>

void ogdf::BinaryHeapSimple< X, INDEX >::clear ( )

inline

empties the heap [O(1)]

Definition at line 70 of file MinHeap.h.

empty()

template<class X , class INDEX = int>

bool ogdf::BinaryHeapSimple< X, INDEX >::empty ( ) const

inline

Returns true if the heap is empty.

Definition at line 64 of file MinHeap.h.

extractMin()

template<class X , class INDEX = int>

X ogdf::BinaryHeapSimple< X, INDEX >::extractMin ( )

inline

Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)].

Definition at line 99 of file MinHeap.h.

getMin()

template<class X , class INDEX = int>

const X & ogdf::BinaryHeapSimple< X, INDEX >::getMin ( ) const

inline

Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as top(), O(1)].

Definition at line 76 of file MinHeap.h.

heapdown()

template<class X , class INDEX = int>

void ogdf::BinaryHeapSimple< X, INDEX >::heapdown ( )

inlineprotected

Definition at line 121 of file MinHeap.h.

heapup()

template<class X , class INDEX = int>

void ogdf::BinaryHeapSimple< X, INDEX >::heapup ( INDEX  idx )

inlineprotected

Definition at line 109 of file MinHeap.h.

insert()

template<class X , class INDEX = int>

void ogdf::BinaryHeapSimple< X, INDEX >::insert ( X &  x )

inline

Adds an element to the heap [Same as push(), O(log n)].

Definition at line 89 of file MinHeap.h.

operator[]()

template<class X , class INDEX = int>

const X & ogdf::BinaryHeapSimple< 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)

Definition at line 102 of file MinHeap.h.

pop()

template<class X , class INDEX = int>

X ogdf::BinaryHeapSimple< X, INDEX >::pop ( )

inline

Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)].

Definition at line 92 of file MinHeap.h.

push()

template<class X , class INDEX = int>

void ogdf::BinaryHeapSimple< X, INDEX >::push ( X &  x )

inline

Adds an element to the heap [Same as insert(), O(log n)].

Definition at line 79 of file MinHeap.h.

size()

template<class X , class INDEX = int>

INDEX ogdf::BinaryHeapSimple< X, INDEX >::size ( ) const

inline

Returns the number of elements in the heap.

Definition at line 67 of file MinHeap.h.

top()

template<class X , class INDEX = int>

const X & ogdf::BinaryHeapSimple< X, INDEX >::top ( ) const

inline

Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as getMin(), O(1)].

Definition at line 73 of file MinHeap.h.

Member Data Documentation

data

template<class X , class INDEX = int>

Array<X, INDEX> ogdf::BinaryHeapSimple< X, INDEX >::data

private

Definition at line 56 of file MinHeap.h.

num

template<class X , class INDEX = int>

INDEX ogdf::BinaryHeapSimple< X, INDEX >::num

private

Definition at line 57 of file MinHeap.h.

---

The documentation for this class was generated from the following file:

• include/ogdf/basic/MinHeap.h