Heap And Priority Queues

PRIORITY QUEUES

What is a complete binary tee?

If you represent a binary tree as an array in a level order traversal, then there should no gaps within it. If there are any gaps, that shows that the tree has missing nodes in the left to right order property of leaf nodes.

If all nodes are there in every level then it is a full binary tree having exactly 2^[h+1] - 1 nodes. But if the last level has null nodes, but it is still completely traversed from left to right level order without any gaps in an array then it is a complete binary tree.

A complete binary tree is also a full binary tree upto height [ h - 1 ] where the elements in the last level are being filled from left to right.

To put simply,

A binary tree without gaps in level order traversal is a complete binary tree. It is also called, an almost complete binary tree.

The height of a complete binary tree will be minimum and always be of [ log n ] because we are not going to the next level unless and until the last level is completely filled.

Let us see some more examples of complete binary trees,

Heaps

A heap is a data structure in the form of a complete binary tree implemented using arrays to store and retrieve values according to their priorities. They are of two types, max and min.

A max heap is such that every node is greater than its descendents and the root node always has the maximum value.

A min heap is such that every node is smaller than its descendents and the root node always has the minimum value.

How heap nodes are stored and accessed through arrays?

The nodes are stored in arrays such that the root is always at the front of the array, which is at index of 1. The left child will always be at multiples of 2 from the position of current node. Similarly, the right child will always be at multiples of 2 + 1 from the position of current node.

The difference of number of nodes from one higher level to a lower level in a complete binary tree is its half, hence accessing the parent node using the floor value of the half of current node is completely valid.

Remember,

IF node = i THEN PARENT [node] = i/2

LEFT [node] = i * 2 AND RIGHT [node] = ( i * 2 ) + 1

Operations on Heap

Let us take max heap as an example,

Insertion Steps

First we take the new element as a leaf node such that the binary tree satisfies the property of a complete binary tree.

Then we adjust the node in heap by comparing it with its ancestors. If the current node is greater than its parent node, it has to be moved upwards.

Nodes are swapped from our inserted node reaching upwards till root, and swapping is stopped once the current node is not greater than its parent node.

Deletion Steps

Only one element can be deleted at a time in the heap, root node, because the root represents the maximum priority in a max heap.

Suppose apples are kept in an hierarchy. The best shiny apples are chosen and always kept on the top. Similarly, our priorities are always kept on the top.

We begin with always removing the root node first and storing it in a temporary node to return it as the deleted node or value.

Then to maintain the complete binary tree property of heaps, we remove the last leaf node, and replace it with the root node.

Then we push that replaced node downwards towards the end, by comparing it with its child nodes. If any of its child nodes are greater than itself, it swaps and moves down.

The node again reaches its correct position when its either reaches the bottom or its child nodes are not greater than itself.

To put simly,

Swaps at Inseration are done at upward direction.

Swaps at deletion are done at downward direction.

The maximum swaps in a heap depends on height.

Heap Sort

To sort an array using heaps, we generally follow two steps.

First, create the heap for a given set of elements. And once it is formed, delete all elements from the heap, and store it in the array each deletion.

Each deleted space from the same array can used to store the sorted array on the back side of the array, thus saving up space.

Let us see an example of heap sort by inserting 10, 20, 15, 30, 40
First, we’ll do the insertions and store values in the heap array.

Then we’ll do the deletions and the sorted array has been received.

The time complexity for complete heap sort is O(2nlogn)
Heapify
The way to inverse an heap from an given heap is using the heapify way, we can effectively change a max heap to a min heap or opp.
It only takes O(n) to handle such operations.
Consider a min heap, how will you make it a max heap?

Procedure

We use the bottom-up approach, beginning from last leaf node. We check for each node whether they have descendents. As leaf nodes have no children, we skip them. Once we reach a parent node from a level lower than the highest level, we compare its descendents from itself. We then swap that node which has a child node greater than itself till we hit the rock bottom.

Dry run

In the above example, we skip 18, 25, 40, 12 as they are leaf nodes. We then move a level up checking 15, and swapping it with 25. Then we compare 20, and swap it with 40 as it is greater. Finally, the last node 10 is compared, and 40 goes to the root. But we haven’t hitted the bottom yet for 10, we compare again, And we swap 10 with 25. Finally we got a max heap !

Priority Queues

Priority queue is just a abstract data type name to the heaps, as it provides the methods such as push(), pop(), offer() similar to queues, but its internal implementation is done using either max heap or min heap.

Priority queues can be implemented using arrays or using trees. Even though the structure looks like tree, but arrays are preferred because the insertion and deletion is fixed at the root of the tree.

Here’s the implementation of max and min heap.

MAX HEAP IMPLEMENTATION IN C

#include<stdio.h>

// The heap size is dynamic. It either grows or shrinks based on the the inserted nodes. In C implementation, the maximum heap size is the number of elements the array can store.

staticint heap_size = 0;

// This function is being used to insert nodes in the max heap order. It works by first adding a node, as the last leaf node, following the complete binary tree principle. They heap_size is incremented, and the value is stored in the array.

// Then we have to do comparisons and swap the nodes. We know that insertion in heap is an upwards approach, also known as the bottom-up approach. We go from bottom till top, checking whether a certain condition holds true.

// We get the index of the parent node, from where the new node has been inserted. We check for a condition if our new node is greater than our parent node, if it is, then we have to swap it and move it upwards, as it is a max heap implementation.

// We have to do the same comparison for swapped node for its ancestor, till our condition is false, and the node reaches its correct place. To reach its ancestor, we half the indexes of parent and current nodes. As we know that the number of nodes in lower level are half of the number of nodes in higher level in a complete binary tree, this is completely valid to find indexes.

// We run the loop till the parent index is the root itself, and then we stop because indexes have been run out.

voidinsert_max_heap(int heap[], int val){
heap[++heap_size] = val;
int current_node_index = heap_size;
int parent_node_index = heap_size / 2;
while(parent_node_index > 0){
if(heap[current_node_index] > heap[parent_node_index]){
int temp = heap[current_node_index];
heap[current_node_index] = heap[parent_node_index];
heap[parent_node_index] = temp;
}
parent_node_index = parent_node_index / 2;
current_node_index = current_node_index / 2;
}
}

// This function deletes the root node of our max heap. It then replaces it with the leaf node. And does a series of comparisons with the replaced value so that it reaches the correct place.

// We begin by storing the leaf_node and decrementing the heap_size, as well as storing the root node. We then replace the root node with the leaf_node, successfully completing the first step.

// The left and right child of the replaced node, are first checked whether they exist or not, to avoid throwing any segmentation faults.

// When we know that either both or one child may exist, we check for the case for two child and one child separately. For one child, the heap tree will always have the node on the left side. One child can never be at right side in a complete binary tree. For two child, either of the two child could be greater than the other, we first compare and find out which one is greater, based on that two cases arise, either left node is greater or right node is greater.

// When the greater node is found out, it is then compared with the actual replaced node at last, to find out whether its children are greater than the replaced node. Because we are using a max heap, greater children must be moved upwards. If that case arises, swap happens.

// As soon as the swap happens, the replaced node now reaches the second level, but the tree could have many levels, and many comparisons would still be remaining, so the replaced node has to do the same comparisons on the new level until either the greater children condition fails or the node reaches rock buttom and becomes leaf. For that, we increment its index by multiples of 2, as we know the number of nodes at a new level are double than the previous level.

intdelete_max_heap(int heap[]){
int i = 1, left, right;
int leaf_node = heap[heap_size--];
int deleted = heap[i];
heap[i] = leaf_node;
left = i * 2;
right = (i * 2) + 1;
while(left <= heap_size || right <= heap_size) {
if(right <= heap_size){ // two child
if(heap[left] > heap[right]){
if(heap[left] > heap[i]){
int temp = heap[i];
heap[i] = heap[left];
heap[left] = temp;
i = i * 2;
} else {
break;
}
} else {
if(heap[right] > heap[i]){
int temp = heap[i];
heap[i] = heap[right];
heap[right] = temp;
i = (i * 2) + 1;
} else {
break;
}
}
} else { // one child [always on left]
if(heap[left] > heap[i]){
int temp = heap[i];
heap[i] = heap[left];
heap[left] = temp;
i = i * 2;
} else {
break;
}
}
left = i * 2;
right = (i * 2) + 1;
}

return deleted;
}

// A simple function to display how the heap nodes are being stored in the array currently by their indexes.

voiddisplay(int heap[]){
for(int i = 1; i <= heap_size; i++){
printf(" %d ", heap[i]);
}
}

// We are sorting the list and displaying it. We have successfully implemented Heap Sort using Max heap.

intmain(){

int e, val;

printf("Enter the list of numbers: ");

scanf("%d", &e);

int heap[e + 1];

heap[0] = 0;

for(int i = 0; i < e; i++){

printf("Enter a number: ");

scanf("%d", &val);

insert_max_heap(heap, val);

}

printf("\n Max heap: ");

display(heap);

int sorted[e];

for(int i = 0; i < e; i++){

printf("\n\n %d deleted ", heap[1]);

sorted[i] = delete_max_heap(heap);

display(heap);

}

printf("\n\n Sorted list: ");

for(int i = 0; i < e; i++){

printf(" %d", sorted[i]);

}

return0;

}

MIN HEAP IMPLEMENTATION IN C

You may find it funny, but the code below is exactly same as above, with no further explanations needed. There is only one change in a min heap implementation. And that is the comparison check for greater value. We replaced the > greater symbol with a < smaller symbol. Boom ! We got the min heap.

#include<stdio.h>
staticint heap_size = 0;
voidinsert_min_heap(int heap[], int val){
heap[++heap_size] = val;
int current_node_index = heap_size;
int parent_node_index = heap_size / 2;
while(parent_node_index > 0){
if(heap[current_node_index] < heap[parent_node_index]){
int temp = heap[current_node_index];
heap[current_node_index] = heap[parent_node_index];
heap[parent_node_index] = temp;
}
parent_node_index = parent_node_index / 2;
current_node_index = current_node_index / 2;
}
}
intdelete_min_heap(int heap[]){
int i = 1, left, right;
int leaf_node = heap[heap_size--];
int deleted = heap[i];
heap[i] = leaf_node;
left = i * 2;
right = (i * 2) + 1;
while(left <= heap_size || right <= heap_size) {
if(right <= heap_size){ // two child
if(heap[left] < heap[right]){
if(heap[left] < heap[i]){
int temp = heap[i];
heap[i] = heap[left];
heap[left] = temp;
i = i * 2;
} else {
break;
}
} else {
int temp = heap[right];
if(heap[right] < heap[i]){
int temp = heap[i];
heap[i] = heap[right];
heap[right] = temp;
i = (i * 2) + 1;
} else {
break;
}
}
} else { // one child [always on left]
if(heap[left] < heap[i]){
int temp = heap[i];
heap[i] = heap[left];
heap[left] = temp;
i = i * 2;
} else {
break;
}
}
left = i * 2;
right = (i * 2) + 1;
}

return deleted;
}
voiddisplay(int heap[]){
for(int i = 1; i <= heap_size; i++){
printf(" %d ", heap[i]);
}
}
intmain(){
int e, val;
printf("Enter the list of numbers: ");
scanf("%d", &e);
int heap[e + 1];
heap[0] = 0;

for(int i = 0; i < e; i++){
printf("Enter a number: ");
scanf("%d", &val);
insert_min_heap(heap, val);
}
printf("\n Min heap: ");
display(heap);

int sorted[e];
for(int i = 0; i < e; i++){
printf("\n\n %d deleted ", heap[1]);
sorted[i] = delete_min_heap(heap);
display(heap);
}

printf("\n\n Sorted list: ");
for(int i = 0; i < e; i++){
printf(" %d", sorted[i]);
}
return0;
}