More Binary Heaps and Heap Sort Algorithm


Hello people…! In this post I will talk about the Binary Heap implemented using structures and not arrays. This is post is the successor to my previous post on Binary Heaps. Using arrays to code Binary Heaps is very comfortable for the programmer. But it is not fit for the day-to-day applications. This is because the Binary Heap is used to implement the Priority Queue and it is meant to grow, not stay of fixed size. But given that it is meant to grow, we cannot use STL Vector for this. This is because the Vector keeps reallocating memory as it grows. So, it is slow. Here we will learn the proper structure based implementation of the Binary Heaps.

Now, currently we have the knowledge of the Binary Heap, its structure, working and other properties. But we implemented this using arrays. Now if we were to implement using a structure, there is one challenge that we will face. That is to ensure the Structural Property of the heap. Why? For insertion into an array, we created a node at the end which itself ensured the Structural Property is not violated and then we bubbled upwards to ensure that the Heap Property is not violated at any point. In the array, we knew exactly where we are supposed to insert the node. But in a tree coded using structures how will you find where to insert the new element such that the tree remains a complete binary tree..? The same goes when we want to delete the root. How do we know where the last node is. For this, we will use the binary representation of the size of the heap to traverse to the location we want.

Size does matter !

While inserting itself we could keep a track of the heap size. So, this takes constant time. While inserting, we must search for the appropriate location. For this, we will convert the size into its binary representation and begin the traversal from the root. How? Keep reading the bits of the binary representation you just generated, if you encounter ‘0’ go to the left child of the parent, if it is a ‘1’ go to the right child of the parent. I know it sounds really weird, but that’s the best thing we can do. Let’s take up an example to understand this better. Consider the Binary Heap below –

BinaryHeaps1

Now consider the binary representation of the number (HeapSize + 1) = 8, which is “1000”. We omit the first bit (left-to-right) because that bit says “come to the root”.

  • The Binary String left is “000”. The leftmost bit is ‘0’. So, go to the Left Child. You come to Node 4.
  • The Binary String left is “00”. The leftmost bit is ‘0’. So, go to the Left Child. You come to Node 1.
  • The Binary String left is “0”. There is only one bit left. This bit doesn’t tell you to “go left” or “go right”, it tells you to “insert it to left” or “insert it to right”. As this bit is “0”, we place the new node as the left child of Node 1.

This is how you must use the binary representation of the (HeapSize + 1) to get to the location you want to insert the node. This is process is depicted in the sketch below –

BinaryHeaps2

Every time you insert a node, you will go all the way down the tree, you will not perform any insertions in the middle, so the traversal always takes O(log n), once inserted, you travel up, ensuring that the heap property holds good, so you have to travel all the way up again, so it is another O(log n) operation. So, the over all process takes O(log n), which is same as in the case of an array implementation.

But for deletion, we are supposed to find something else. We are supposed to find out the last node. In the sketch above, before the insertion of 8, we are supposed to somehow find out that the last node is Node 5. There are a couple of methods by which we can accomplish this –

  1. BFS or DFS – By using the Breadth First Search or the Depth First Search we can find out which is the last node in the Binary Heap by searching the whole tree for a node at the maximum depth which is encountered as last as possible. The time complexity of BFS and DFS is O(|E| + |V|). We would have N vertices and what about the number the edges? We would have N – 1 edges, because every node is pointed by a child pointer, except the root. So, the overall complexity becomes O(N + N), which is O(N).
  2. Binary Traversal – This is the same traversal as we did in the case of Insertion. I just called it Binary Traversal. But the method which we discussed about gave us the Node to be inserted but not the last node. Can you think of a way of modifying the procedure such that it would give us the last node directly…? Think about this for a couple of minutes and you will figure out the simple logic behind it. For those who can’t, don’t worry I will discuss it, when I do, try to figure how silly a thing you missed…! The logic is simple, you used the binary representation of (HeapSize + 1) to get to the location where you were supposed to insert a node, if you use the binary representation of (HeapSize) itself for traversal, you will end up at the last node…! Try working out this on paper and you will realise the logic behind it. As, we would traverse the whole tree from root to leaf, this takes O(log N), which is way faster than BFS and DFS which was an O(N) operation. This kind of Binary Traversal is depicted in the sketch below –

BinaryHeaps3

The next thing that we must know about the structure implementation is that unlike the array implementation, where we could construct the heap using build heap procedure, we cannot do that here. The only way to construct the heap from a given collection of numbers is to keep inserting them one-by-one. As we discussed that in insertion, we would have to go all the way down and come up, inserting a node in the structure implementation will be slower than inserting into a heap implemented using arrays.

So, now let us plan what we would be writing as our code. First things first..! The structure of our nodes in the heap would be –

struct node
{
	int value;
	struct node * parent;
	struct node * leftChild;
	struct node * rightChild;
};

Apart from the standard variables that we see in many structure related codes, we would be needing the parent pointer here. This is because, without that, we cannot travel up the tree, which is needed in insertion and deletion.

Heap Sort – If you have understood the concepts of constructing the Binary Heap, finding the Last Node and Extracting maximum element, then Heap Sort becomes obvious. You just have to keep extracting the maximum element and store it in an array or a list. Then, you will have a sorted array. This essentially destroys the entire heap.

Take a break and come back to code the binary heap. If you have already coded the binary search tree or a binary tree before this should be relatively easy for you. If you have not, then this will be challenging, and I’m sure you’ll be proud of your efforts once you have successfully coded this data structure. You will spend 80% of the time debugging your code, and trust me that’s the way programming is done. I can’t discuss the issues that you might encounter while coding but you can always comment them if you need help. Once you are able to code Insertion and Deletion, Heap Sort should be easy. If you get stuck, you can always refer to my code below –

/*
 * Binary Heap using Structures
 * and Heap Sort Algorithm
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <cstdio>
#include <cstdlib>
#include <list>

using namespace std;

struct node
{
	int value;
	struct node * parent;
	struct node * leftChild;
	struct node * rightChild;
};

// Traverses the Heap top-to-bottom once and returns the location
// of the last node. Works on the priciple of traversing a
// Binary Tree by the binary representation of its size.
struct node * findLastNode(struct node * BinaryHeap, int size)
{
	list<int> Stack;

	// Getting the binary
	// representation of the size
	while (size != 0) {
		if (size & 1) {
			Stack.push_front(true);
		} else {
			Stack.push_front(false);
		}

		size = size >> 1;
	}

	// Omit the first bit
	Stack.pop_front();

	struct node * traverse = BinaryHeap;
	bool temp;

	while (Stack.size() != 0) {
		temp = Stack.front();
		Stack.pop_front();

		if (temp) {
			// encountered 1
			// go to rightChild
			traverse = traverse->rightChild;
		} else {
			// encountered 0
			// go to leftChild
			traverse = traverse->leftChild;
		}
	}

	return traverse;
}

// This makes the neccessary adjustments
// after insertion to ensure the validity
// of Heap Property in the Binary Heap
void bubbleUp(struct node * heap)
{
	if (heap->parent == NULL) {
		return;
	}

	if (heap->parent->value < heap->value) {
		// Swap child and parent
		int temp = heap->value;
		heap->value = heap->parent->value;
		heap->parent->value = temp;

		bubbleUp(heap->parent);
	}
}

// The recursive procedure which goes top-to-bottom from the root to the place of
// insertion and inserts the new node with a value 'Value'. Uses binary traversal.
struct node * insertUtil(struct node * BinaryHeap, int value, list<bool> * Stack)
{
	bool temp;

	if ((*Stack).size() == 1) {
		temp = (*Stack).front();
		(*Stack).pop_front();

		if (temp) {
			// create new node as the right child
			BinaryHeap->rightChild = (struct node *) calloc(1, sizeof(struct node));
			BinaryHeap->rightChild->parent = BinaryHeap;
			BinaryHeap = BinaryHeap->rightChild;
			BinaryHeap->value = value;
		} else {
			// create new node as the left child
			BinaryHeap->leftChild = (struct node *) calloc(1, sizeof(struct node));
			BinaryHeap->leftChild->parent = BinaryHeap;
			BinaryHeap = BinaryHeap->leftChild;
			BinaryHeap->value = value;
		}
	} else {
		temp = (*Stack).front();
		(*Stack).pop_front();

		if (temp) {
			// encountered 1
			// go to rightChild
			BinaryHeap = insertUtil(BinaryHeap->rightChild, value, Stack);
		} else {
			// encountered 0
			// go to leftChild
			BinaryHeap = insertUtil(BinaryHeap->leftChild, value, Stack);
		}
	}

	return BinaryHeap;
}

// Inserts a new node into the binary heap and also makes
// the neccessary swaps to ensure Heap Property isn't violated
void insertIntoHeap(struct node * BinaryHeap, int value, list<bool> * Stack)
{
	(*Stack).pop_front(); // Omit the first bit

	// Inserting into Heap and keeping a
	// track of the newly inserted node
	struct node * newNode = insertUtil(BinaryHeap, value, Stack);

	// Bubble the new node up the
	// Heap to ensure validity of
	// the Heap Property
	bubbleUp(newNode);
}

// Allocates memory for the Binary
// Heap thus creates the root node
struct node * getBinaryHeap(int value)
{
	struct node * BinaryHeap = (struct node *) calloc(1, sizeof(struct node));

	BinaryHeap->value = value;

	return BinaryHeap;
}

// A simple utility function
// to aid In-Order Walk
void print(struct node * BinaryHeap)
{
	printf("%d ", BinaryHeap->value);
}

// Prints the nodes of the Binary
// Heap in the In-Order fashion
void inOrderTraversal(struct node * BinaryHeap)
{
	if (BinaryHeap == NULL) {
		return;
	}

	inOrderTraversal(BinaryHeap->leftChild);
	print(BinaryHeap);
	inOrderTraversal(BinaryHeap->rightChild);
}

// The standard recursive Heapify procedure to
// convert a partial heap to a complete heap
// Mainly used by Extract-Max procedure
void heapify(struct node * BinaryHeap)
{
	if (BinaryHeap->leftChild != NULL && BinaryHeap->rightChild != NULL) {
		// both children exist

		if (BinaryHeap->value < BinaryHeap->leftChild->value && BinaryHeap->value < BinaryHeap->rightChild->value) {
			if (BinaryHeap->leftChild->value > BinaryHeap->rightChild->value) {
				// leftChild is greater

				int temp = BinaryHeap->value;
				BinaryHeap->value = BinaryHeap->leftChild->value;
				BinaryHeap->leftChild->value = temp;

				heapify(BinaryHeap->leftChild);
			} else {
				// rightChild is greater

				int temp = BinaryHeap->value;
				BinaryHeap->value = BinaryHeap->rightChild->value;
				BinaryHeap->rightChild->value = temp;

				heapify(BinaryHeap->rightChild);
			}
		} else if (BinaryHeap->value < BinaryHeap->leftChild->value && BinaryHeap->value > BinaryHeap->rightChild->value) {
			// leftChild is greater & rightChild is smaller than parent

			int temp = BinaryHeap->value;
			BinaryHeap->value = BinaryHeap->leftChild->value;
			BinaryHeap->leftChild->value = temp;

			heapify(BinaryHeap->leftChild);
		} else if (BinaryHeap->value > BinaryHeap->leftChild->value && BinaryHeap->value < BinaryHeap->rightChild->value) {
			// rightChild is greater & leftChild is smaller than parent

			int temp = BinaryHeap->value;
			BinaryHeap->value = BinaryHeap->rightChild->value;
			BinaryHeap->rightChild->value = temp;

			heapify(BinaryHeap->rightChild);
		}
	} else if (BinaryHeap->rightChild == NULL && BinaryHeap->leftChild != NULL) {
		// Only the leftChild exists

		if (BinaryHeap->leftChild->value > BinaryHeap->value) {
			// The existing leftChild is greater than parent
			// So swap

			int temp = BinaryHeap->leftChild->value;
			BinaryHeap->leftChild->value = BinaryHeap->value;
			BinaryHeap->value = temp;
		}

		// When we reach here, logically speaking, we have come
		// to the last node in the Binary Heap, so after this
		// we simply return from the function
	}
}

// Returns the root value and deletes it by swapping the root
// node and the last node and then calling heapify on root node
int extractMax(struct node * BinaryHeap, struct node * lastNode)
{
	if (BinaryHeap == NULL) {
		return -1;
	}

	if (BinaryHeap == lastNode) {
		// A corner case where only
		// one node exists

		int max = BinaryHeap->value;

		free(BinaryHeap);

		return max;
	}

	int max = BinaryHeap->value;

	// Swap root node and last node
	int temp = BinaryHeap->value;
	BinaryHeap->value = lastNode->value;
	lastNode->value = temp;

	// Making its parent point to NULL appropriately
	struct node * parent = lastNode->parent;

	if (parent->leftChild == lastNode) {
		parent->leftChild = NULL;
	} else {
		parent->rightChild = NULL;
	}

	// Deleting the lastNode
	free(lastNode);
	heapify(BinaryHeap);	// making adjustments

	return max;
}

// Heap Sort procedure which takes and empyt list 'Sorted List'
// and fills it with the elements in sorted order. Keeps extracting
// the maximum element from the Max Heap until it is empty
void heapSort(struct node * BinaryHeap, list<int> * SortedList, int HeapSize)
{
	struct node * lastNode;
	list<int>::iterator itr;

	while (HeapSize != 0) {
		//getting the lastNode to assist extractMax procedure
		lastNode = findLastNode(BinaryHeap, HeapSize);
		(*SortedList).push_front(extractMax(BinaryHeap, lastNode));
		--HeapSize;
	}
}

int main()
{
	int n;

	printf("Enter the size of input -\n");
	scanf("%d", &n);

	int temp, i, j, HeapSize = 0;
	struct node * BinaryHeap;
	list<bool> Stack;

	printf("\nEnter %d integers -\n", n);

	for (i = 0; i < n; ++i) {
		scanf("%d", &temp);
		++HeapSize;

		if (i == 0) {
			BinaryHeap = getBinaryHeap(temp);
			continue;
		}

		// Clears the Stack before filling it with
		// the Binary Representation of HeapSize
		Stack.clear();
		j = HeapSize;

		while (j != 0) {
			if (j & 1) {
				Stack.push_front(true);
			} else {
				Stack.push_front(false);
			}

			j = j >> 1;
		}

		insertIntoHeap(BinaryHeap, temp, &Stack);
	}

	printf("\nIn Order Traversal - ");
	inOrderTraversal(BinaryHeap);
	printf("\n");

	list<int> SortedList;

	heapSort(BinaryHeap, &SortedList, HeapSize);
	BinaryHeap = NULL;

	list<int>::iterator itr = SortedList.begin();

	printf("\nElements in Sorted order - ");
	while (itr != SortedList.end()) {
		printf("%d ", *itr);
		++itr;
	}
	printf("\n");

	return 0;
}

The code is big and that is how it should be and moreover, it is well commented with information. If you still have doubts regarding the code or any concept, feel free to comment them. I hope my post has helped you to get a complete idea about the Binary Heap. If it did, let me know by commenting…! Keep practising… Happy Coding…! 🙂

You may also like –

More in the Navigation Page ! →

Advertisements

Dijkstra’s Algorithm


Hello people…! In this post I will talk about one of the fastest single source shortest path algorithms, which is, the Dijkstra’s Algorithm. The Dijkstra’s Algorithm works on a weighted graph with non-negative edge weights and ultimately gives a Shortest Path Tree. It is a Greedy Algorithm, which sort of… mimics the working of Breadth First Search and Depth First Search. It is used in a number of day-to-day scenarios. It is used in network routing, to calculate the path from a network device A and B in a network which would have the maximum bandwidth. It could also be used by the GPS in a car to calculate the shortest path between two locations. The Dijkstra’s Algorithm can be modified to solve a lot of real world problems. So let’s get started…!

The Dijkstra’s Algorithm starts with a source vertex ‘s‘ and explores the whole graph. We will use the following elements to compute the shortest paths –

  • Priority Queue Q, implemented by a Min Binary Heap using C++ STL Vector.
  • Another set D, which keeps the record of the shortest paths from starting vertex s. Implemented using C++ STL Vector.

Just like the other graph search algorithms, Dijkstra’s Algorithm is best understood by listing out the algorithm in a step-by-step process –

  • The Initialisation –
  1. D(s), which is the shortest distance to s is set to 0. It is obvious as distance between source to itself is 0.
  2. For all the other vertices V, D(V) is set to infinity as we do not have a path yet to them, so we simply say that the distance to them is infinity.
  3. The Priority Queue Q, is constructed which is initially holds all the vertices of the Graph. Each vertex V will have the priority D(V).
  • The Algorithm –
  1. Now, pick up the first (or the minimum) element from the Priority Queue Q (which removes it from Q). For the first time, this operation would obviously give s.
  2. For all the vertices adjacent to s, i.e., for all vertices in adjacencyMatrix[s], check if the edge from s → v gives a shorter path. This is done by checking the following condition –

    if, D(s) + (weight of edge s → v) < D(v), we found a new shorter route, so update D(v)
    D(v) = D(s) + (weight of edge s → v)

  3. Now pick the next element from Q, and repeat the process until there are elements left in Q.

It might look like a long and cumbersome process, but this is actually a very smart technique. It’s okay if you don’t understand it in the first reading. Give another 3-4 readings and try to picture what is happening to the graph when you implement the algorithm, in your head. After you feel you have got a hang of the algorithm, look at the sketch below for complete understanding.

Dijkstra's Algorithm Step-by-Step

Dijkstra’s Algorithm Step-by-Step

 

The Dijkstra’s Algorithm is a little tricky. Many don’t understand it in the first attempt. In reference to the diagram above, I will give a step-by-step explanation for each graph marked with the number on top in purple.

  1. Firstly, initialize your components, the shortest distances array D, the priority queue Q, and starting vertex s. The distance from source to itself is zero. So, D(s) = 0, and the rest of the array is ∞ . The set of vertices V are inserted into the priority queue Q, with a priority D(V). Now, we start our algorithm by extracting (hence removing it from the priority queue) the minimum element from the priority queue. The minimum element in the priority queue will definitely be s (which is A here). Look at all the adjacent vertices of A. Vertices B, C, D are adjacent to A. We can go to B travelling the edge of weight 2, to C travelling an edge of weight 1, to D travelling an edge of weight 5. The values of D(B), D(C), D(D) are ∞ . We have found a new way of reaching them in 2, 1, 5 units respectively, which is less than ∞ , hence a shorter path. This is what the if-condition mentioned above does. So, we update the values of D(B), D(C), D(D) and the priorities of B, C, D, in the priority queue. With this we have finished processing the Vertex A.
  2. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element would be Vertex C which would be having a priority of 1. Now, look at all the adjacent vertices to C. There’s Vertex D. From C, the it would take 1 unit of distance to reach D. But to reach C in prior, you need 1 more unit of distance. So, if you go to D, via C, the total distance would be 2 units, which is less than the current value of shortest distance discovered to D, D(D) = 5. So, we reduce the value of D(D) to 2. This reduction is also called as “Relaxation”. With that we’re done with Vertex C.
  3. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. Now, there are two minimum elements, B and D. You can go for anyone, it doesn’t matter. For now, we will go for Vertex D. From Vertex D, you can go to Vertex E, and Vertex F, with a total distance of 2 + 2 {D(D) + (weight of D → E)}, and 2 + 3. Which is less than ∞ , so D(E) becomes 4 and D(F) becomes 5. We’re done with Vertex D.
  4. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex B. From vertex B, you can reach vertex F in 2 + 1 units of distance, which is less than the current value of D(F), 5. So, we relax D(F) to 3. From vertex B, you can reach vertex D in 2 + 2 units of distance, which is more than the current value of D(D), 2. This route is not considered as it is clearly proven to be a longer route. With that we’re done with vertex B.
  5. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex E. From vertex E, you can reach vertex C in 4 + 4 units of distance, which is more than the current value of D(C), 1. This route is not considered as it is clearly proven to be a longer route. With that we’re done with vertex E.
  6. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex F. You cannot go to any other vertex from vertex F, so, we’re done with vertex F.
  7. With the removal of vertex F, our priority queue becomes empty. So, our algorithm is done…! You can simply return the array D to output the shortest paths.

Having got an idea about the overall working of the Dijkstra’s Algorithm, it’s time to look at the pseudo-code –

dijsktra(G, S)
	D(S) = 0
	Q = G(V)

	while (Q != NULL)
		u = extractMin(Q)
		for all V in adjacencyList[u]
			if (D(u) + weight of edge < D(V))
				D(V) = D(u) + weight of edge
				decreasePriority(Q, V)

In the pseudo-code, G is the input graph and S is the starting vertex. I hope you understand the pseudo-code. If you don’t, feel free to comment your doubts. Now, before we code Dijkstra’s Algorithm, we must first prepare a tool, which is the Priority Queue.

The Priority Queue

The Priority Queue is implemented by a number of data structures such as the Binary Heap, Binomial Heap, Fibonacci Heap, etc. The priority queue in my code is implemented by a Binary Heap. If you are not aware about the Binary Heap, you can refer to my post on Binary Heaps. But the implementation that we will do here is different from that in my post regarding the Binary Heap. The difference is that, here we will implement the Binary Heap using C++ STL Vector, not an array. This is because a heap is meant to grow, not remain of a fixed size, so we are using a data structure that can grow, a vector. Also, when we use a vector we can apply the same traversing techniques that we used in the case of an array. And, every element of our vector will be a Pair of two integers from the utility header file. The two integers represent vertex and weight, which is actually the shortest distances and this weight property will function as the priority to the elements. So, the vertices are placed in the priority queue based on their weight property. We will have to code the operations based on this weight property. Now the functionalities that we need from our priority queue are –

  • Insert – We will insert |V| elements into the Priority Queue.
  • Extract Min – We return the top-most element from the Binary Heap and delete it. Finally we make the neccessary
  • Decrease Priority – We decrease the priority of an element in the priority queue when we find a shorter path, as known as Relaxation.

If you know the working of the Binary Heap and have a little knowledge about the STL Library, you can code the Priority Queue in about 2-5 hours. You can keep referring to the internet of various functions and the syntaxes and any other doubts you have. Typing the code doesn’t take long, but debugging it and making it work takes the most time. That’s how you learn coding. Try your best, work on it for hours, if you don’t get it, take a break for 10-20 minutes… Come back and check my code below and try to figure out how close you were to getting it perfect…!

/*
 * Priority Queue implemented
 * by a Binary Heap using
 * C++ STL Vector, for
 * Dijkstra's Algorithm
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

// Inserts an element into the Queue
void enqueue(vector< pair<int, int> > * priorityQueue, pair<int, int> * entry)
{
	(*priorityQueue).push_back(*entry);

	int i = (*priorityQueue).size() - 1;
	pair<int, int> temp;

	while (i > 0) {
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;

			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Iterates over the Queue to return the index of the element
int findByKey(vector< pair<int, int> > * priorityQueue, pair<int, int> entry)
{
	int i;

	for (i = 0; i < (*priorityQueue).size(); ++i) {
		if ((*priorityQueue)[i].first == entry.first) {
			break;
		}
	}

	if (i != (*priorityQueue).size()) {
		return i;
	} else {
		return -1;
	}
}

// Decreases the priority of the element and makes neccessary adjustments
void decreasePriority(vector< pair<int, int> > * priorityQueue, int index, int newWeight)
{
	(*priorityQueue)[index].second = newWeight;

	int i = index;
	pair<int, int> temp;

	while (i > 0) {
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;

			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Returns the minimum element, deletes it and makes neccessary changes
pair<int, int> extractMin(vector< pair<int, int> > * priorityQueue)
{
	pair<int, int> min = (*priorityQueue)[0];
	pair<int, int> temp;

	// Swap first and last
	temp = (*priorityQueue)[0];
	(*priorityQueue)[0] = (*priorityQueue)[(*priorityQueue).size() - 1];
	(*priorityQueue)[(*priorityQueue).size() - 1] = temp;

	(*priorityQueue).pop_back();

	int i = 0;
	pair<int, int> parent;
	pair<int, int> rightChild;
	pair<int, int> leftChild;

	while (i < (*priorityQueue).size()) {
		parent = (*priorityQueue)[i];
		printf("Currently at - (%d, %d)\n", parent.first, parent.second);

		if (2 * (i + 1) < (*priorityQueue).size()) {
			// both children exist
			rightChild = (*priorityQueue)[2 * (i + 1)];
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];

			if (parent.second < leftChild.second && parent.second < rightChild.second) {
				break;
			} else {
				if (leftChild.second < rightChild.second) {
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;

					i = 2 * (i + 1) - 1;
				} else {
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;

					i = 2 * (i + 1);
				}
			}
		} else if ((2 * (i + 1)) >= (*priorityQueue).size() && (2 * (i + 1) - 1) < (*priorityQueue).size()) {
			// only left child exists
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];

			if (leftChild.second < parent.second) {
				temp = (*priorityQueue)[2 * (i + 1) - 1];
				(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
				(*priorityQueue)[i] = temp;
			}

			break;
		} else {
			// no more children exist
			break;
		}
	}

	return min;
}

int main()
{
	int n;

	printf("Enter the size -\n");
	scanf("%d", &n);

	int vertex, weight, i;
	vector< pair<int, int> > priorityQueue;
	pair<int, int> entry;

	for (i = 0; i < n; ++i) {
		scanf("%d%d", &vertex, &weight);
		entry = make_pair(vertex, weight);
		enqueue(&priorityQueue, &entry);
	}

	printf("\n\nThe Priority Queue (Interpret as Binary Heap) -\n");

	vector< pair<int, int> >::iterator itr = priorityQueue.begin();

	while (itr != priorityQueue.end()) {
		printf("(%d, %d) ", (*itr).first, (*itr).second);
		++itr;
	}
	printf("\n");

	pair<int, int> min = extractMin(&priorityQueue);
	printf("\n\nExtract Min returned = (%d, %d), The Queue -\n", min.first, min.second);
	itr = priorityQueue.begin();

	while (itr != priorityQueue.end()) {
		printf("(%d, %d) ", (*itr).first, (*itr).second);
		++itr;
	}
	printf("\n");

	decreasePriority(&priorityQueue, priorityQueue.size() - 1, 1);
	printf("\n\ndecreasePriority() used, The Queue -\n");
	itr = priorityQueue.begin();

	while (itr != priorityQueue.end()) {
		printf("(%d, %d) ", (*itr).first, (*itr).second);
		++itr;
	}
	printf("\n");

	return 0;
}

There are many other functionalities that a Priority Queue can give. But for now, we’ll need only these.

Joining the pieces

After you have your tool ready, you are all good to code Dijkstra’s Algorithm. Coding the Dijkstra’s Algorithm is easy but can go really weird. This is because you need to handle and co-ordinate many data structures at once. You’ll have to manage the adjacency list, the priority queue, the shortest distance array, and most importantly your loops…! You will surely end up spending more time in debugging the code, which is perfectly the right way of doing it. All throughout the coding, keep revising the step-by-step process explained above. If you don’t get it you, don’t fret, I put my code below. Before you look at my code, I would like to mention a few things –

  • We cannot have infinity in programming, so the shortest distances are initialised to the highest possible value in integer range, present in a macro, INT_MAX, in the header file climits.
  • The header file utility must be included to use pairs.
/* 
 * Dijkstra's Algorithm in C++
 * using Binary Heap as Priority
 * Queue implemented using 
 * C++ STL Vector
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <vector>
#include <utility>

using namespace std;

// Our Vertex for Graph
struct node {
	int vertex, weight;
	struct node * next;
};

// To construct our Adjacency List
// Follows Head Insertion to give O(1) insertion
struct node * addEdge(struct node * head, int vertex, int weight)
{	 
	struct node * p = (struct node *) calloc(1, sizeof(struct node));
	
	p->vertex = vertex;
	p->weight = weight;
	p->next = head;
	
	return p;
}

// Adds vertices to the Priority Queue, Vertices a represented
// as pairs of vertex number and its shortest distance.
// This is logically a Binary Heap Insertion
void enqueue(vector< pair<int, int> > * priorityQueue, pair<int, int> * entry)
{
	(*priorityQueue).push_back(*entry);
	
	int i = (*priorityQueue).size() - 1;
	pair<int, int> temp;
	
	while (i > 0) {
		// Checking the priority of the parent, if greater, swap, else, we are done
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;
			
			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Finds for a Vertex in the Priority Queue and 
// returns its index as in its vector implementation
int findByKey(vector< pair<int, int> > * priorityQueue, pair<int, int> entry)
{
	int i;
	
	// Linear Search
	for (i = 0; i < (*priorityQueue).size(); ++i) {
		if ((*priorityQueue)[i].first == entry.first) {
			break;
		}
	}
	
	if (i != (*priorityQueue).size()) {
		return i;
	} else {
		return -1;
	}
}

// Decreases the priority of a given entry in the
// Priority Queue who's location is given by 'index'
// to 'newWeight' and re-arranges the Binary Heap
void decreasePriority(vector< pair<int, int> > * priorityQueue, int index, int newWeight)
{
	// Decreasing Priority
	(*priorityQueue)[index].second = newWeight;
	
	int i = index;
	pair<int, int> temp;
	
	// Adjusting the Binary Heap, similar re-arrangement as done in enqueue()
	while (i > 0) {
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;
			
			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Picks up the minimum element of the Priority Queue and re-arranges
// the Binary Heap and finally returns the Minimum Element picked.
// Functionally resembles Delete operation in Binary Heap, but additionally
// returns the deleted element which is the minimum element.
pair<int, int> extractMin(vector< pair<int, int> > * priorityQueue)
{
	pair<int, int> min = (*priorityQueue)[0];		// Min Element Stored
	pair<int, int> temp;
	
	// Swap first and last elements
	temp = (*priorityQueue)[0];
	(*priorityQueue)[0] = (*priorityQueue)[(*priorityQueue).size() - 1];
	(*priorityQueue)[(*priorityQueue).size() - 1] = temp;
	
	(*priorityQueue).pop_back();					// Deleted Min Element
	
	int i = 0;
	pair<int, int> parent;			// These three variables
	pair<int, int> rightChild;		// are for readability of
	pair<int, int> leftChild;		// the if conditions ahead
	
	while (i < (*priorityQueue).size()) {
		parent = (*priorityQueue)[i];
		
		if (2 * (i + 1) < (*priorityQueue).size()) {
			// both children exist
			rightChild = (*priorityQueue)[2 * (i + 1)];
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];
			
			if (parent.second < leftChild.second && parent.second < rightChild.second) {
				// Parent has lesser priority than its children, so wer're done
				break;
			} else {
				if (leftChild.second < rightChild.second) {
					// Left-child has a lesser priority, so, swap
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;
				
					i = 2 * (i + 1) - 1;
				} else {
					// Right-child has a lesser priority, so, swap
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;
				
					i = 2 * (i + 1);
				}
			}
		} else if ((2 * (i + 1)) >= (*priorityQueue).size() && (2 * (i + 1) - 1) < (*priorityQueue).size()) {
			// only left child exists
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];
			
			if (leftChild.second < parent.second) {
				// Left-child has a lesser priority, so, swap
				temp = (*priorityQueue)[2 * (i + 1) - 1];
				(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
				(*priorityQueue)[i] = temp;
			}
			
			break;
		} else {
			// no more children exist
			break;
		}
	}
	
	return min;
}

// The Dijkstra's Algorithm sub-routine which takes the Graph as Adjcaency List,
// number of vertices, a starting vertex, and an empty shortestDistances array as
// input and computest the shortest paths and fills them up in the shortestDistances array
void dijkstra(struct node * adjacencyList[], int vertices, int startVertex, pair<int, int> shortestDistances[])
{
	int i;
	
	// Initially no routes to vertices are know, so all are infinity,
	// here, we initialize to a very high integer value
	for (i = 0; i <= vertices; ++i) {
		shortestDistances[i].first = INT_MAX;
		shortestDistances[i].second = -1;
	}
	
	// Setting distance to source to zero
	shortestDistances[startVertex].first = 0;
	shortestDistances[startVertex].second = 0;
		
	struct node * trav;
	vector< pair<int, int> > priorityQueue;
	pair<int, int> min;
	
	// Making a the vertex that corresponds to the
	// 'startVertex' which will have a priority of zero
	// and we begin to intialise the Priority Queue
	pair<int, int> entry = make_pair(startVertex, 0);
	enqueue(&priorityQueue, &entry);
	
	// Initialising Priority Queue
	for (i = 1; i <= vertices; ++i) {
		if (i == startVertex) {
			continue;
		} else {
			// Priorities are set to a high integer value
			entry = make_pair(i, INT_MAX);
			enqueue(&priorityQueue, &entry);
		}
	}

	// We have the tools ready..! Let's roll...!!
	while (priorityQueue.size() != 0) {		// Untill there are vertices to be processed in Queue
		min = extractMin(&priorityQueue);	// Greedily process the nearest vertex
		
		trav = adjacencyList[min.first];	// Checking all the vertices adjacent to 'min'
		while (trav != NULL) {
			if (shortestDistances[trav->vertex].first > shortestDistances[min.first].first + trav->weight) {
				// We have discovered a new shortest route
				// Make the neccesary adjustments in data
				entry = make_pair(trav->vertex, trav->weight);
				
				int index = findByKey(&priorityQueue, entry);
				
				decreasePriority(&priorityQueue, index, trav->weight);
				shortestDistances[trav->vertex].first = shortestDistances[min.first].first + trav->weight;
				shortestDistances[trav->vertex].second = min.first;
			}
			
			trav = trav->next;
		}
	}
}

void PrintShortestPath(pair<int, int> shortestDistances[], int vertex, int startVertex)
{
	if (vertex == startVertex) {
		printf("%d ", startVertex);
		return;
	} else {
		PrintShortestPath(shortestDistances, shortestDistances[vertex].second, startVertex);
		printf("%d ", vertex);
	}
}

int main()
{
	int vertices, edges, i, j, v1, v2, w;
	
	printf("Enter the Number of Vertices -\n");
	scanf("%d", &vertices);
	
	printf("Enter the Number of Edges -\n");
	scanf("%d", &edges);
	
	struct node * adjacencyList[vertices + 1];
	//Size is made (vertices + 1) to use the
	//array as 1-indexed, for simplicity
	
	//Must initialize your array
	for (i = 0; i <= vertices; ++i) {
		adjacencyList[i] = NULL;
	}
	
	printf("\n");
	
	for (i = 1; i <= edges; ++i) {
		scanf("%d%d%d", &v1, &v2, &w);
		adjacencyList[v1] = addEdge(adjacencyList[v1], v2, w);
	}
 
 	//Printing Adjacency List
	printf("\nAdjacency List -\n\n");
	for (i = 1; i <= vertices; ++i) {
		printf("adjacencyList[%d] -> ", i);
		
		struct node * temp = adjacencyList[i];
		
		while (temp != NULL) {
			printf("%d(%d) -> ", temp->vertex, temp->weight);
			temp = temp->next;
		}
		
		printf("NULL\n");
	}
	
	int startVertex;
	
	printf("Choose a Starting Vertex -\n");
	scanf("%d", &startVertex);
	
	pair<int, int> shortestDistances[vertices + 1];
	// shortestDistances.first = shortest distance calculated
	// shortestDistances.second = parent node
	
	dijkstra(adjacencyList, vertices, startVertex, shortestDistances);
	
	printf("\n\nDijkstra's Algorithm Used - Shortest Paths from Vertex %d -\n", startVertex);
	for (i = 1; i <= vertices; ++i) {
		printf("Vertex %d, Distance = %d, Parent = %d\n", i, shortestDistances[i].first, shortestDistances[i].second);
	}
	printf("\n");
	
	PrintShortestPath(shortestDistances, vertices /* The Last Vertex */, startVertex);
	
	return 0;
}

This is the Dijkstra’s Algorithm. The code is well commented with explanation. If you don’t understand anything or if you have any doubts. Feel free to comment them. Now talking about the complexity of Dijkstra’s Algorithm. We perform |V| enqueue operations into the priority queue, which take O(log N), here, N is |V|, so this takes O(|V| log |V|). And at most |E| decrease priority operations which will take O(|V|) time. The extract-min is also called |V| times which will take O(|V| log |V|) time. So, the overall complexity of Dijkstra’s Algorithm we wrote is O(|V| log |V| + |E||V|). Dijkstra’s Algorithm can be improved by using a Fibonacci Heap as a Priority Queue, where the complexity reduces to O(|V| log |V| + |E|). But the Fibonacci Heap is an incredibly advanced and difficult data structure to code. We’ll talk about that implementation later.

I really hope my post has helped you in understanding the Dijkstra’s Algorithm. If it did, let me know by commenting. I tried my best to keep it as simple as possible. If you have any doubts, you can comment them too and I will surely reply to them. This algorithm is a particularly tough one. So, good luck… Keep practicing and… Happy Coding…! 🙂

You may also like –

More in the Navigation Page ! →

Binary Heaps


Hello people…! In this post I will talk about Binary Heaps, or, more casually called as Heaps. Binary Heaps are used to implement Priority Queues which are associated with Scheduling. Binary Heaps is a starting step to learn many advanced heap related Data Structures that are used in many algorithms. So let’s understand the need of the situation by taking up a scenario.

Let’s say that the CPU has to execute ‘n’ programs that take their own pre-defined time to get completed. Then one strategy to schedule them is the Shortest Remaining Processing Time (SRPT) first method. As the name suggests, we look at all the available programs, then pick up that program which takes the minimum time to get executed. After completing that program, then the next minimum is supposed to be picked up. So if we observe what operations are we doing on the data we have, they would be –

  • Finding the minimum of given elements.
  • Deleting the minimum element (after a program gets executed).
  • Inserting a new element (if a new program enters the scheduling).

So, we must choose such a Data Structure which takes the minimum to these operations so that we can come up with an efficient solution to the scenario. Binary Heap is one such Data Structure that does these operations in pretty fast time. Now, what exactly is the Binary Heap…? What does it look like…? The Binary Heap is actually a Binary Tree has two very important properties –

  • Structural Property – The value of every node in the Binary Tree should be less than or equal to the values of its children nodes.
  • Heap Property – The Binary Tree should be fully-filled up to the 2nd last level and the last level must be “left-filled”.

To understand these two properties let’s take up an example –

heaps1 (2)

So, as we can see, the last level is what is called “left-filled”, i.e., all the nodes are to the left and all the empty spaces to the right. The heap property is also depicted. The parent is smaller than both of its children. Now, having introduced this structure to you. Can you think where the smallest element of the heap would be….? At the top of course…! This is due to the very definition of the Heap Property. If the parent has the lower number, then the ancestor of all the nodes should surely have the least number. But this does not say that the leaves at the last level have the greatest number. Think about it for a while looking at the picture and you will understand it.

Now, the Binary Heap is although depicted as a tree, it is implemented as an array…! Just like the Fenwick Tree. The Binary Tree structure of the allows this. Look at the sketch below –

heaps2

As, you can see, the nodes of the heap are put into an array in the left-to-right order at each level. Why is this so…? This is the way we can access all the nodes in a heap. How…? If we take any element arr[i] –

  • Parent of Element at i → arr[ i2 ]
  • Left Child of Element at → arr[(2 ✕ i)]
  • Right Child of Element at → arr[(2 ✕ i) + 1]

Looking at the picture, we can verify the above statements. For example, take the node 9 (arr[6]) which is at level 3. Its parent is arr[ 92 ] which is arr[3], i.e., node 6 at level 2, as it is in the structure. The left child of arr[6] is arr[(2 ✕ 6)], which is, arr[12], node 20 and like this even the right child can be verified. The way to find the parent is actually floor( i2 ), but as both ‘i’ and 2 are integers the result comes as it is desired. Now, we must discuss the five important operations in a binary heap –

  • Getting minimum element
  • Inserting a new element
  • Deleting a new Element
  • Heapify
  • Build Heap

Minimum Element – As you can clearly see, the minimum element would be the topmost element of the heap which is the first element of the array. So this operation takes O(1) time.

Inserting an Element – Recall that the last level of the heap must be left-filled. So, where ever you add a node, the resulting structure should be such that the last level will have an extra element. We do this, by first adding the new element to the end, then to ensure that the Structural Property is satisfied we keep swapping the element with its parent until the parent node to be swapped is less than the inserted element. So, we kind of insert the element at the bottom and we “move up” the heap. This process is illustrated in the sketch below.

heaps3

This is how we insert a node into a heap. In the worst case we would have to travel all the way up which costs us (log n) swaps, which is the height of the tree. So, the insertion operation has a complexity of O(log n).

Deleting an Element – Deleting an element is also similar to Inserting the element. Structurally, when an element is deleted, the last level will lose the right-most node. So what we do is, we swap the last element and the node to be deleted, then remove the last element. And carry the swapped element up the heap just as we did in Insertion so that the Heap Property is not violated. This is illustrated in the sketch below –

heaps4

This is how the Deletion Operation is done in a Binary Heap. As you can clearly analyse that the worst case would be if we have to swap elements all the way up the Binary Heap, where the Deletion Operation would take O(log n) time.

Heapify – The heapify operation is as the name suggests, converting some “non-heap” thing into a heap. Well what this non-heap thing is that, it is a parent node, where the left and the right children are heaps, but the structure as a whole isn’t a heap. How is that possible…? This parent node we are talking about, its value could be greater than one or both of its children. In such a case, the smaller valued child is swapped with the parent and this is carried on down the tree until the heap property holds true for the whole structure. To understand this, observe the sketch below.

heap5

The process of heapify is clearly shown in the sketch, how we keep swapping the child nodes till the heap property is satisfied for the whole structure. This too takes O(log n) time in the worst case, when we would have to travel the whole till the leaves. Where is this process used anyway…? It is used to build a heap, which is our next discussion.

Build Heap – Build heap is constructing the heap from a given set of randomly arranged nodes in a binary tree. The build heap process uses the heapify to construct the heap “down-to-up”. Now, if you remember the principle of the heapify process, we were able to do that only because the left-subtree and the right-subtree were heaps. Think of the second last level in a heap, the left and the right nodes are leaves, i.e., they have no children, so, they are heaps by themselves. Why is a leaf by itself a heap…? This is because the left child and the right child don’t exist, so we can claim that the parent node (the leaf), satisfies the heap property. And for a leaf, the structural property also holds good because the second-last level, (the level of the leaf node), is fully filled, and the last level (the level of the leaf’s children), is left-filled (actually there are no nodes to be left-filled). Well, most probably, you won’t understand this in the first reading, give it another couple of readings and observe the picture below.

heaps6

I hope the process of the Build Heap is clear. At every level we use the heapify process to gradually build the heap “down-up”. So what is the asymptotic time complexity of Build Heap…? We use heapify for all the nodes except the nodes in the last level,

Nodes till the 2nd Last level = 12 ✕ (Total number of Nodes ⇒ N)
Complexity of the Heapify procedure = O(log N)
Complexity of Build Heap = O(N log N)

But we can argue that the Build Heap process will only take O(N). Now, look at the above sketch once again. If you feel the text is too small, open the image by right-clicking, its bigger than you think…! Now,

The (n + 1)4 nodes at level 3 took 1 swap ⇒ (n + 1)4 ✕ 1
The (n + 1)8 nodes at level 2 took 2 swaps ⇒ (n + 1)8 ✕ 2
The (n + 1)16 nodes at level 1 took 3 swaps ⇒ (n + 1)16 ✕ 3

As, you can see, we have a sort-of progression here. If we were to sum them up, taking (n + 1) common,

⇒ (N + 1) ✕ (14 + 28 + 316 + …)
⇒ (N + 1) ✕ Σ i2i
⇒ (N + 1) ✕ 2       { Σ i2i = 2 }
⇒ O(N)

Therefore, the Build Heap takes O(N) time. The principle behind this is that for most of the time Heapify works on smaller values of ‘N’. These are the most important operations of a Binary Heap. We have discussed the implementation of Binary Heaps using arrays and accessing the parent and child. Now, try to code the above stated operations at least 3 times…! You have to try. There is no better way of knowing a Data Structure than trying to code it. After you have given your everything, if you succeed, you are brilliant…! If not, look at my code below and see for yourselves how close you were…!

/* ==========  ========== ========== ========= */
//        Binary Min Heap Data Structure       //
//           Array Implementation              //
//                                             //
//         Functions follow Pascal Case        //
//           Convention and Variables      	   //
//         follow Camel Case Convention        //
//                                             //
//            Author - Vamsi Sangam            //
//            Theory of Programming            //
/* ========== ========== ========== ========== */
 
#include <stdio.h>
#include <stdlib.h>

struct Vertex
{
	int label, value;
};

// Adds an element to the heap and returns the size - O(log N)
int EnqueueVertex(struct Vertex minHeap[], int size, struct Vertex newValue)
{
    ++size;
    minHeap[size] = newValue;
 
    int i = size;
	struct Vertex temp;
 
    while (i >= 1) {
        if (minHeap[i / 2].value > minHeap[i].value) {
            // Parent node is greater than Child Node
            // Heap Property violated
            // So, swap
            temp = minHeap[i / 2];
            minHeap[i / 2] = minHeap[i];
            minHeap[i] = temp;
 
            i = i / 2;
        } else {
            // Parent is less or equal to the child
            // Heap property not violated
            // So, Insertion is done, break
            break;
        }
    }
 
    return size;
}

// Applies the heapify procedure - O(log N)
void Heapify(struct Vertex minHeap[], int size, int index)
{
    int i = index;
	struct Vertex temp;
 
    while ((2 * i) <= size) {
        // Left Child exists
 
        if ((2 * i) + 1 > size) {
            // Right child does not exist, but left does
            
			if (minHeap[i].value > minHeap[2 * i].value) {
                // Left child is smaller than parent
                temp = minHeap[i];
                minHeap[i] = minHeap[2 * i];
                minHeap[2 * i] = temp;
            }
            
            break;
            // Once you reach this level where it does not
        	// have a right child, the heap ends here
            // taking it to the next iteration is pointless
        }
 
        //Both Children exist
        if (minHeap[i].value > minHeap[2 * i].value || minHeap[i].value > minHeap[2 * i + 1].value) {
            // One of the other child is lesser than parent
            // Now find the least amoung 2 children
 
            if (minHeap[2 * i].value <= minHeap[(2 * i) + 1].value) {
                // Left Child is lesser, so, swap
                temp = minHeap[2 * i];
                minHeap[2 * i] = minHeap[i];
                minHeap[i] = temp;
 
                // And go down the heap
                i = 2 * i;
            } else if (minHeap[2 * i].value > minHeap[(2 * i) + 1].value) {
                // Left Child is lesser, so, swap
                temp = minHeap[(2 * i) + 1];
                minHeap[(2 * i) + 1] = minHeap[i];
                minHeap[i] = temp;
 
                // And go down the heap
                i = (2 * i) + 1;
            }
        } else {
            // Parent is lesser than its children
            break;
        }
    }
}

// Deletes the vertex and returns the size - O(log N)
int DeleteVertex(struct Vertex minHeap[], int size, int index)
{
    // Swap the indexed element with the last
    struct Vertex temp = minHeap[index];
    minHeap[index] = minHeap[size];
    minHeap[size] = temp;
 
    int i = index;
    --size;
 
    Heapify(minHeap, size - 1, i);
 
    return size;
}

// Build Heap Procedure - O(N)
void BuildHeap(struct Vertex minHeap[], int size)
{
    int i;
 
    // Simply call heapify() for all nodes
    // except the last one...!
    for (i = size / 2; i >= 1; --i) {
        Heapify(minHeap, size, i);
    }
}
 
int main()
{
    int n, i;
 
    printf("Enter the Initial size of the Min Heap -\n");
 
    scanf("%d", &n);
 
    struct Vertex minHeap[n + 2];
    // Extra size just to demonstrate Insertion
    // and use the array as 1-indexed
    
    printf("Enter %d elements -\n", n);
 
    for (i = 1; i <= n; ++i) {
        scanf("%d%d", &minHeap[i].label, &minHeap[i].value);
    }
 
    BuildHeap(minHeap, n);
 
    printf("\nHeap -\n");
    for (i = 1; i <= n; ++i) {
        printf("%d, %d\n", minHeap[i].label, minHeap[i].value);
    }
 
	struct Vertex node;
	
    printf("\n\nInsert an element -\n");
    scanf("%d%d", &node.label, &node.value);
    n = EnqueueVertex(minHeap, n, node);
 
    printf("\nHeap After Insert -\n");
    for (i = 1; i <= n; ++i) {
        printf("%d, %d\n", minHeap[i].label, minHeap[i].value);
    }
 
    printf("\n\nDelete an Element at index-\n");
    scanf("%d", &i);
    n = DeleteVertex(minHeap, n, i);
 
    printf("\nHeap After Delete -\n");
    for (i = 1; i <= n; ++i) {
        printf("%d, %d\n", minHeap[i].label, minHeap[i].value);
    }
 
    return 0;
}

One thing I would like to point out is that, my heap is an array of structures. Just an integer would suffice, but I made it an array of structures so that it becomes a little generic. So, tomorrow, if you want to you this code as a Priority Queue, you needn’t change anything (or at most the names) in the code. Or, if you wanted to store more information about each node of the Binary Heap, you can simply add attributes to the struct.
Next, for my deletion operation, I swapped the last element and the element to be deleted and called the heapify procedure. This is because, the heapify procedure, checks if the Heap Property is violated and makes the necessary corrections. As the first element of the heap is the smallest, it can be accessed directly by heap[1]. Remember, the arrays in my code are 1-indexed, and all the loops and conditions go with it.
The code is pretty well tested. You can download the input file here.

There is one last topic to discuss before I conclude.

Max Heap – Whatever heaps we have been seeing till now are all Min Heaps. This is because, the Heap Property is such that the minimum element is put on top. What if the Heap Property would just be the reverse of it…? Something like –

Heap Property – Every parent node must have a value greater than or equal to both of its child node.

In this case, by the Heap property, the maximum element would be put on the top and so will be for all the sub-trees or sub-heaps in the structure. This is a Max Heap. Actually, the very first heap that we used in our Build Heap sketch is a Max Heap. Have a close look at it and you will understand the difference. Max Heap differ from Min Heaps only by the Heap Property, due to which the other differences arise.

Whoo…! This has become a really long post…! Thanks a lot to stay with me till the end. I hope this helps you to get started with heaps. It may not be easy to code the Binary Heap, but that’s how you grow your skills in programming. You won’t learn anything if you sit for hours and write the Hello World program over-and-over again. You need to challenge yourself…! Feel free to comment your doubts..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practicing…! Happy Coding…! 🙂