Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

An In-Depth Look At Binary Heaps

Icon 1 Comments
Similar to Binary Search Trees, a heap is a collections of nodes, of which only have, at most, two children. Typically there is an ordering scheme which provides a great deal of functionality. The code in this post is for a "max heap". This means that any time a node is inserted or removed, the heap will adjust itself so that the largest value will always be the "root". (A min heap is the exact opposite of this).

A textbook definition if you please, Mr. Wiki:

Quote

A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
* The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
* The heap property: each node is greater than or equal to each of its children according to some comparison predicate which is fixed for the entire data structure.


In layman's terms, we are going to ensure that the heap is never unbalanced (we'll accomplish this by using an array backed heap and always inserting at the end [first open space] of that array) and shifting the heap to ensure that every node is less then its parent and the root is the largest.

An Array Backed Heap

Unlike the post on BSTs, each node does not contain references/handles to its children. We use a simple mathematical relationship to obtain the children for a node at a given index, which is as follows:

a[i]'s children:
a[2i+1] left
a[2i+2] right

a[i]'s parent:
a[floor((i+1/2))]

Which looks like this:

Attached Image

NOTE: This is for an array implementation that starts at zero. You can start at one and just discard/ignore the first index, but the formulas will be slightly different.


Heap Order Property

As already mentioned, the example presented is a max heap. We'll keep track of how much space we have (the size of the array) in addition to the actual number of elements we have in the heap (the heap size). To maintain the max heap property, this is the pseudo code of insertion and removal:

Insertion
Add node to the first available "spot". This is the "end" of the heap.
Percolate up
If the node above is less then the node we just inserted, swap places.
Move up a level
Repeat until you at the top or the node above is greater [heap condition is satisfied].


Visually:

Inserting 4, 10, 43, 100, 15

Attached Image

Removal

Removal always "pops" the root off, aka the largest item.
Swap the largest item with the last item in the heap (heapsize-1 index).
Delete the heapsize-1 node and set its pointer to NULL
Now that the lowest item is on top:
Percolate down
Check to see if the node has any children
if so, check to see what is larger
if the child is larger, swap and continue percolating down until there are no more children or the heap condition is satisfied



A visual:

Attached Image


Now let's see some code!

The HeapNode:

#ifndef HEAPNODE_H
#define HEAPNODE_H

template<class T>
class HeapNode{
private:
	T data;
public:
	HeapNode();
	HeapNode(T);
	~HeapNode();
	T getData()						{return data;};
};

//*****IMPLEMENTATION******
template<class T>
HeapNode<T>::HeapNode(){
	data = NULL;
}

template<class T>
HeapNode<T>::HeapNode(T data){
	this->data = data;
}

template<class T>
HeapNode<T>::~HeapNode(){
}
#endif



Not a lot going on here, all the node does is tell the Heap what it's carrying.


The BinaryHeap:

#ifndef BINARYHEAP_H
#define BINARYHEAP_H
#include "HeapNode.h"

//MAX HEAP
template<class T>
class BinaryHeap{
private:
	HeapNode<T>** storage; //array backed heap
	int arrSize;
	int heapSize;

	//helper functions
	void percolateUp(int);
	void percolateDown(int);
	void inOrder(int);
	void postOrder(int);
	void preOrder(int);
	int numChildren(int);

	bool isEmpty();
public:
	BinaryHeap(int);
	~BinaryHeap();

	//heap operations
	void insertNode(T);
	T removeMax(); //or pop()?


	//traversal
	void inOrderTraversal();
	void postOrderTraversal();
	void preOrderTraversal();
	void linearDisplay();
};

//******IMPLEMENTATION********

template<class T>
BinaryHeap<T>::BinaryHeap(int size){
	storage = new HeapNode<T>*[size];
	for(int i = 0; i < size; i++) storage[i] = NULL;
	arrSize = size;
	heapSize = 0;
}

template<class T>
BinaryHeap<T>::~BinaryHeap(){
	//used for debugging, could just use heapSize as the conditional
	int usedCount = heapSize;
	for(int i = 0; i < usedCount; i++){
		if(storage[i] != NULL) delete storage[i]; //free each node, if applicable
		heapSize--;
	}
	//for debug purposes
	cout << "heap size is (should be zero): " << heapSize << endl;
	delete[] storage;
}

template<class T>
void BinaryHeap<T>::insertNode(T data){
	if(heapSize == arrSize){
		cerr << "No more room in this heap!" << endl;
		return;
	}

	HeapNode<T>* temp = new HeapNode<T>(data);
	//insert at end
	heapSize++;
	storage[heapSize-1] = temp;
	percolateUp(heapSize-1);
}

template<class T>
void BinaryHeap<T>::percolateUp(int curIndex){
	int parentIndex;
	HeapNode<T>* temp;
	if(curIndex != 0) { //are we at the "top"?
		parentIndex = (curIndex-1)/2;
		//max heap
		//if the parent is "less then" the child, it violates our heap property
		//perk up!
		if(storage[parentIndex]->getData() < storage[curIndex]->getData()){
			temp = storage[parentIndex];
			storage[parentIndex] = storage[curIndex];
			storage[curIndex] = temp;
			percolateUp(parentIndex);
		}
	}
}


template<class T>
T BinaryHeap<T>::removeMax(){
	if(isEmpty()) {
		cout << "Heap is empty!" << endl;
		return NULL;
	}
	T value = storage[0]->getData();
	HeapNode<T>* temp = storage[0];
	//replace max with last filled node slot (heapSize-1)
	//perc down
	storage[0] = storage[heapSize-1];
	storage[heapSize-1] = temp;
	delete storage[heapSize-1]; //free
	storage[heapSize-1] = NULL; //avoid dangling pointers
	heapSize--;
	percolateDown(0);
	return value;
}

template<class T>
void BinaryHeap<T>::percolateDown(int curIndex){
	int children = 0;
	if(children = numChildren(curIndex)){ //are we at the "bottom"?
		HeapNode<T>* temp;
		int left = 2*curIndex+1, right = 2*curIndex+2;
		switch(children){ //1 child or 2 children
			case 1:
				//if the child is larger, perk the current node down
				if(storage[curIndex]->getData() < storage[left]->getData()){
					temp = storage[curIndex];
					storage[curIndex] = storage[left];
					storage[left] = temp;
					percolateDown(left);
				}
				break;
			case 2:
				//2 children, determine which is larger, perk down that direction
				if((storage[curIndex]->getData() < storage[left]->getData()) || 
							(storage[curIndex]->getData() < storage[right]->getData())){
					//left child is greater
					if((storage[left]->getData() > storage[right]->getData())){
						temp = storage[curIndex];
						storage[curIndex] = storage[left];
						storage[left] = temp;
						percolateDown(left);
					}
					else{ //right child is greater
						temp = storage[curIndex];
						storage[curIndex] = storage[right];
						storage[right] = temp;
						percolateDown(right);
					}
				}
				break;
			default:
				cout << "wtf? this shouldn't happen" << endl;
				break;
		}
	}
	return;
}

template<class T>
void BinaryHeap<T>::inOrderTraversal(){
	if(isEmpty()){
		cout << "Heap is empty!" << endl;
		return;
	}
	inOrder(0);
	cout << endl;
}

template<class T>
void BinaryHeap<T>::inOrder(int curIndex){
	//left
	//cur
	//right
	if(((2*curIndex+1) < arrSize) && (storage[2*curIndex+1] != NULL)) inOrder(2*curIndex+1);
	cout << storage[curIndex]->getData() << " ";
	if(((2*curIndex+2) < arrSize) && (storage[2*curIndex+2] != NULL)) inOrder(2*curIndex+2);
}

template<class T>
void BinaryHeap<T>::postOrderTraversal(){
	if(isEmpty()){
		cout << "Heap is empty!" << endl;
		return;
	}
	postOrder(0);
	cout << endl;
}

template<class T>
void BinaryHeap<T>::postOrder(int curIndex){
	//left
	//right
	//cur
	if(((2*curIndex+1) < arrSize) && (storage[2*curIndex+1] != NULL)) inOrder(2*curIndex+1);
	if(((2*curIndex+2) < arrSize) && (storage[2*curIndex+2] != NULL)) inOrder(2*curIndex+2);
	cout << storage[curIndex]->getData() << " ";
}

template<class T>
void BinaryHeap<T>::preOrderTraversal(){
	if(isEmpty()){
		cout << "Heap is empty!" << endl;
		return;
	}
	preOrder(0);
	cout << endl;
}

template<class T>
void BinaryHeap<T>::preOrder(int curIndex){
	//cur
	//left
	//right
	cout << storage[curIndex]->getData() << " ";
	if(((2*curIndex+1) < arrSize) && (storage[2*curIndex+1] != NULL)) inOrder(2*curIndex+1);
	if(((2*curIndex+2) < arrSize) && (storage[2*curIndex+2] != NULL)) inOrder(2*curIndex+2);
}


template<class T>
void BinaryHeap<T>::linearDisplay(){
	for(int i = 0; i < heapSize; i++){
		cout << storage[i]->getData() << " ";
	}
	cout << endl;
}

//handy for percolating, saves us some long conditional checks
template<class T>
int BinaryHeap<T>::numChildren(int index){
	int children = 0, left = 2*index+1, right = 2*index+2;
	if(left >= heapSize) return 0;
	if(storage[left] != NULL) children++;
	if (storage[right] != NULL) children++;
	return children;
}


template<class T>
bool BinaryHeap<T>::isEmpty(){
	return (heapSize == 0);
}
#endif



There might be a few debug type comments or statements lingering about.


The driver:

#include <iostream>
#include "BinaryHeap.h"
using namespace std;


int main(){
	{
		BinaryHeap<int>* test = new BinaryHeap<int>(5);
		test->insertNode(4);
		test->insertNode(10);
		test->insertNode(43);
		test->insertNode(100);
		test->insertNode(15);
		cout << "Before removal [in order traversal]: " << endl;
		test->inOrderTraversal();
		cout << endl << endl;
		cout << "Popped: " << test->removeMax() << endl << endl;
		cout << "After removal [in order traversal]: " << endl;
		test->inOrderTraversal();
		cout << endl << endl;
		delete test;
	}
	cin.get();
	return 0;
}



Output:

Quote

Before removal [in order traversal]:
4 43 15 100 10


Popped: 100

After removal [in order traversal]:
4 15 43 10


heap size is (should be zero): 0


The extraneous local brackets are there to allow us to verify all the memory was freed via tracer statements in the destructor; feel free to remove.


--

This concludes yet another chapter in KYA's data structure adventures. Happy coding!

1 Comments On This Entry

Page 1 of 1

alias120 Icon

22 December 2010 - 04:23 AM
Very nice, thank you for sharing this.
0
Page 1 of 1

October 2014

S M T W T F S
   1 2 34
567891011
12131415161718
19202122232425
262728293031 

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    1 user(s) viewing

    1 Guests
    0 member(s)
    0 anonymous member(s)