DHeap Class Reference

A n-ary tree data structure used by Dijkstra's shortest path algorithm. More...

#include <Network.hpp>

Public Member Functions
	DHeap ()
	Default constructor. More...
	DHeap (unsigned long size, unsigned int d)
	Constructor specifying heap maximum size. More...
	DHeap (unsigned int d, long node_id, std::map< long, Node > &Nodes)
	Constructor specifying heap maximum size and its root node (with key = 0). More...
virtual	~DHeap ()
	Destructor. More...
void	insert (Node &element)
	Insert a node in the heap. More...
void	pushBack (Node &element)
	Insert a node at the end of the heap. More...
const Node	deletemin ()
	Return the node's id with maximum priority (i.e. the first of the heap) and removes it. More...
void	decreaseKey (int index, float key)
	Decrease the key of a given Node and update the heap structure. More...
std::map< long, int >	getMapNodeidIndex () const
	Return the map <node id, node index>. More...
int	size ()
	Compute the size of the heap. More...

Private Member Functions
int	parent (int child)
	Return the index of the parent of child node. More...
int	child (int parent, int ith)
	Return the index of i-th child of a node. More...
void	heapifyup (int index)
	Ensure the heap invariant (bottom -> up), used to add a node to the heap. More...
void	heapifydown (int index)
	Ensure the heap invariant (up -> bottom), used during removal of a node. More...

Private Attributes
std::vector< Node >	heap
	heap of Node. More...
std::map< long, int >	_map_nodeid_index
	map of the node's id and their respective index. More...
int	_d
	degree of the heap, i.e. maximum number of childxs More...

Detailed Description

A n-ary tree data structure used by Dijkstra's shortest path algorithm.

DHeap is a n-ary tree that stores priorities (or priority-element pairs) at the nodes. It has the following properties:

• All levels except last level are full. Last level is left filled.
• Priority of a node is at least as large as that of its parent. A heap can be thought of as a priority queue. The most important node will always be at the root of the tree.

References: http://www.cprogramming.com/tutorial/computersciencetheory/heap.html

Constructor & Destructor Documentation

DHeap::DHeap

(

)

Default constructor.

DHeap::DHeap	(	unsigned long	size,
		unsigned int	d
	)

Constructor specifying heap maximum size.

/param size heap's size (preallocating memory) /param d the maximum number of child for each nodes

DHeap::DHeap	(	unsigned int	d,
		long	node_id,
		std::map< long, Node > &	Nodes
	)

Constructor specifying heap maximum size and its root node (with key = 0).

Parameters

d	degree of the heap
node_id	root node id
Nodes	set of the network's nodes (used to get its size)

DHeap::~DHeap ( )

virtual

Destructor.

Member Function Documentation

int DHeap::child ( int  parent, int  ith  )

private

Return the index of i-th child of a node.

Parameters

parent	parent id
ith	index of the child

void DHeap::decreaseKey	(	int	index,
		float	key
	)

Decrease the key of a given Node and update the heap structure.

Parameters

index	index of the node whose key is to be decreased
key	new key value of the node

const Node DHeap::deletemin

(

)

Return the node's id with maximum priority (i.e. the first of the heap) and removes it.

Returns

the node associated with the minimum key

std::map<long, int> DHeap::getMapNodeidIndex ( ) const

inline

Return the map <node id, node index>.

Returns

the heap's map <node id, node index>

void DHeap::heapifydown ( int  index )

private

Ensure the heap invariant (up -> bottom), used during removal of a node.

When a node is removed which is always the root (lowest in priority) the last available node in heap is replaced as the root and heapifydown process is done. The key of parent node is compared with the children. If any of the children have lower priority it is swapped with the parent. The process is repeated for the newly swapped node till the heap property is met again.

Parameters

index

starting heap index of the procedure

void DHeap::heapifyup ( int  index )

private

Ensure the heap invariant (bottom -> up), used to add a node to the heap.

To add a node, it is inserted at the last empty space and heapifyup process is done. When a node is added, its key is compared to its parent. If parent key is smaller than the current node it is swapped. The process is repeated till the heap property is met.

Parameters

index

starting heap index of the procedure

void DHeap::insert

(

Node &

element

)

Insert a node in the heap.

Parameters

element

the node to insert in the heap.

int DHeap::parent ( int  child )

private

Return the index of the parent of child node.

Parameters

child

id

void DHeap::pushBack

(

Node &

element

)

Insert a node at the end of the heap.

Parameters

element

the node to be inserted at the end of the heap.

int DHeap::size ( )

inline

Compute the size of the heap.

Returns

size of the heap

Member Data Documentation

int DHeap::_d

private

degree of the heap, i.e. maximum number of childxs

std::map<long,int> DHeap::_map_nodeid_index

private

map of the node's id and their respective index.

std::vector<Node> DHeap::heap

private

heap of Node.

---

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

• /home/johan/Documents/UNamur/VirtualBelgium/Workspace/VirtualBelgium/include/Network.hpp
• /home/johan/Documents/UNamur/VirtualBelgium/Workspace/VirtualBelgium/src/Network.cpp