Min-heap priority queue realized by a data array. More...

#include <ogdf/basic/BinaryHeap2.h>

Inheritance diagram for ogdf::BinaryHeap2< key, HeapObject >:

Classes
struct	HeapEntry

Public Member Functions
	BinaryHeap2 (int startSize=128)
	Creates a binary heap.
virtual	~BinaryHeap2 ()
int	capacity () const
	Returns the current size.
void	clear ()
	Reinitializes the data structure.
virtual void	decreaseKey (int index, key priority)
	Decreases priority of an object that is addressed by index.
int	empty () const
	Returns true iff the heap is empty.
HeapObject	extractMin ()
	Returns minimum priority element and removes it from the heap.
key	getPriority (int index) const
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	minRet () const
	Returns minimum priority element.
const BinaryHeap2 &	operator= (const BinaryHeap2< key, HeapObject > &rhs)
	Assignment operator.
int	size () const
	Returns the number of stored elements.
Public Member Functions inherited from ogdf::HeapBase< key, HeapObject >
	HeapBase ()
	Constructor.
virtual	~HeapBase ()
virtual void	decreaseKey ()
	update the data structure by decreasing the key of an object
virtual void	insert (HeapObject, key)
	insert a new element with priority key
HeapObject	minRet ()

Protected Member Functions
int	arrayBound (int arraySize)
bool	hasLeft (int num)
	Returns true if left child exists.
bool	hasRight (int num)
	Returns true if right child exists.
int	higherArrayBound (int arraySize)
int	higherArraySize (int arraySize)
void	init (int initSize)
int	leftChildIndex (int num)
	Array index of left child.
int	lowerArrayBound (int arraySize)
int	lowerArraySize (int arraySize)
int	parentIndex (int num)
	Array index of parent node.
int	rightChildIndex (int num)
	Array index of right child.
void	siftDown (int pos)
	Establishes heap property by moving element down in heap if necessary.
void	siftUp (int pos)
	Establishes heap property by moving element up in heap if necessary.

Private Attributes
int	m_arraySize
HeapEntry *	m_heapArray
int	m_startSize

Additional Inherited Members
Protected Attributes inherited from ogdf::HeapBase< key, HeapObject >
int	m_size

Detailed Description

template<class key, class HeapObject>
class ogdf::BinaryHeap2< key, HeapObject >

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:

key is the key type.
HeapElement is the type of the elements that are stored.

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.

Running Time

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 105 of file BinaryHeap2.h.

Constructor & Destructor Documentation

template<class key , class HeapObject >

ogdf::BinaryHeap2< key, HeapObject >::BinaryHeap2 ( int startSize = 128 )

Creates a binary heap.

Definition at line 293 of file BinaryHeap2.h.

template<class key, class HeapObject>

virtual ogdf::BinaryHeap2< key, HeapObject >::~BinaryHeap2 ( )

inlinevirtual

Definition at line 115 of file BinaryHeap2.h.

Member Function Documentation

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::arrayBound ( int arraySize )

inlineprotected

Definition at line 220 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::capacity ( ) const

inline

Returns the current size.

Definition at line 158 of file BinaryHeap2.h.

template<class key , class HeapObject >

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 314 of file BinaryHeap2.h.

template<class key, class HeapObject >

void ogdf::BinaryHeap2< key, HeapObject >::decreaseKey	(	int	index,
		key	priority
	)

virtual

Decreases priority of an object that is addressed by index.

Definition at line 418 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::empty ( ) const

inline

Returns true iff the heap is empty.

Reimplemented from ogdf::HeapBase< key, HeapObject >.

Definition at line 164 of file BinaryHeap2.h.

template<class key , class HeapObject >

HeapObject ogdf::BinaryHeap2< key, HeapObject >::extractMin ( )

Returns minimum priority element and removes it from the heap.

Definition at line 433 of file BinaryHeap2.h.

template<class key, class HeapObject>

key ogdf::BinaryHeap2< key, HeapObject >::getPriority ( int index ) const

inline

Definition at line 151 of file BinaryHeap2.h.

template<class key, class HeapObject>

bool ogdf::BinaryHeap2< key, HeapObject >::hasLeft ( int num )

inlineprotected

Returns true if left child exists.

Definition at line 205 of file BinaryHeap2.h.

template<class key, class HeapObject>

bool ogdf::BinaryHeap2< key, HeapObject >::hasRight ( int num )

inlineprotected

Returns true if right child exists.

Definition at line 212 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::higherArrayBound ( int arraySize )

inlineprotected

Definition at line 221 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::higherArraySize ( int arraySize )

inlineprotected

Definition at line 222 of file BinaryHeap2.h.

template<class key , class HeapObject >

void ogdf::BinaryHeap2< key, HeapObject >::init ( int initSize )

protected

Definition at line 301 of file BinaryHeap2.h.

template<class key, class HeapObject>

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.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::leftChildIndex ( int num )

inlineprotected

Array index of left child.

Definition at line 191 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::lowerArrayBound ( int arraySize )

inlineprotected

Definition at line 223 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::lowerArraySize ( int arraySize )

inlineprotected

Definition at line 224 of file BinaryHeap2.h.

template<class key , class HeapObject >

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 408 of file BinaryHeap2.h.

template<class key, class HeapObject>

HeapObject ogdf::BinaryHeap2< key, HeapObject >::minRet ( ) const

inline

Returns minimum priority element.

Definition at line 149 of file BinaryHeap2.h.

template<class key, class HeapObject>

const BinaryHeap2< key, HeapObject > & ogdf::BinaryHeap2< key, HeapObject >::operator= ( const BinaryHeap2< key, HeapObject > & rhs )

Assignment operator.

Definition at line 495 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::parentIndex ( int num )

inlineprotected

Array index of parent node.

Definition at line 184 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::rightChildIndex ( int num )

inlineprotected

Array index of right child.

Definition at line 198 of file BinaryHeap2.h.

template<class key , class HeapObject >

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.

template<class key , class HeapObject >

void ogdf::BinaryHeap2< key, HeapObject >::siftUp ( int pos )

protected

Establishes heap property by moving element up in heap if necessary.

Definition at line 327 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::size ( ) const

inline

Returns the number of stored elements.

Reimplemented from ogdf::HeapBase< key, HeapObject >.

Definition at line 161 of file BinaryHeap2.h.

Member Data Documentation

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::m_arraySize

private

Definition at line 277 of file BinaryHeap2.h.

template<class key, class HeapObject>

HeapEntry* ogdf::BinaryHeap2< key, HeapObject >::m_heapArray

private

Definition at line 272 of file BinaryHeap2.h.

template<class key, class HeapObject>

int ogdf::BinaryHeap2< key, HeapObject >::m_startSize

private

Definition at line 279 of file BinaryHeap2.h.

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

ogdf/basic/BinaryHeap2.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class key, class HeapObject> class ogdf::BinaryHeap2< key, HeapObject >

Running Time

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework

template<class key, class HeapObject>
class ogdf::BinaryHeap2< key, HeapObject >