Priority Queue Heaps

Priority Queue Heaps

There are some important properties that should be followed by heap.

1. There should be either "complete binary tree" or "almost complete binary tree".

2. The root of a heap always contains largest element(for a max heap) or a smallest element(for a min heap).

This is heap because 20 is largest among all node values.

3. Each subtree in a heap is also a heap. The tree and subtrees are shown by dotted lines. Each tree/subtree itself is a heap.

• The index of the left or the right child of the parent node is simple expressions. For a zero-based array, the root is stored at index 0. If i is the index of the current node, then, use following formula -

PARENT(i)=floor((i-1)/2)

LEFT-CHILD(i) = 2 x i + 1

RIGHT_CHILD(i) = 2 x i + 2

Min Heap Property: A[PARENT[i]] <=A[i]

Max Heap Property: A[PARENT[i]]> =A[i]

• This representation of heap is called priority queue representation.

• Priority queue is ADT(Abstract Data Type) in which there is a collection of elements with each element having priority associated with it. In priority queue, the high priority elements are served before the low priority elements.

Ex. 4.15.1 For a given heap, give the array representation of it.

Sol. Root node is stored at 0^th index. For each parent node i we will store left node at (21+ 1) and right node at (2i + 2) positions in array.

The array will then be

Ex. 4.15.2 Draw a tree for given heap represented by an array.

Insertion of Element

The algorithm for inserting an element in the heap can be as given below

Algorithm for insertion of element :

1. Insert element at the last position in heap.

2. Compare with its parent, swap the two nodes if parental dominance condition gets violated.

[Parental dominance=Parent is greater than its children]

3. Continue comparing the new element with nodes up, each time by satisfying parental dominance condition.

For example:

If we have to insert 18 to the heap

Step 1

In top down approach the heap is constructed from top to bottom scanning of a tree, each time checking parent dominance property.

Program for insertion of a node in Heap

#include <stdio.h>

#define MAX 50// Max size of Heap

 void heapify(int Heap[], int n, int i)

{

int parent=(i-1)/2;//obtain parent node

if (Heap[parent] > 0)

{

if (Heap[i] >Heap[parent])

{//if current node is greater than parent

int temp=Heap[i]; //swap them

Heap[i] = Heap[parent];

Heap[parent]= temp;

heapify(Heap, n, parent);

}

}

}

void Insert(int Heap[], int& n, int Key)

{

n = n + 1;//size of heap is increased by 1

Heap[n-1] = Key;//insertion of node

heapify(Heap, n, n - 1);

}

void display(int Heap[], int n)

{

for (int i = 0; i < n; ++i)

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

}

int main()

{

int a[MAX];

int n,key;

printf("\n Creating a heap");

printf("\nHow many elements are there? ");

scanf("%d",&n);

printf("\n Enter the elements: ");

for(int i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

printf("\n The heap is as follows...\n");

display(a, n);

printf("\n Enter the element to be inserted in the heap: ");

scanf("%d", &key);

Insert(a, n, key);

printf("\n After insertion the heap is as follows ...\n");

display(a, n);

return 0;

}

Output

Creating a heap

How many elements are there? 6

Enter the elements:

14

12

9

8

7

10

The heap is as follows...

14 12 9 8 7 10

Enter the element to be inserted in the heap: 18

After insertion the heap is as follows.

18 12 14 8 7 10 9

Time complexity

The insertion operation takes O(n) time where n is number of elements in a binary heap.

Deletion of Element

Algorithm for deletion of element from heap:

The root of a heap can be deleted and the heap fixed up can be as follows:

1. Exchange the root with the last leaf.

2.Decrease the heap's size by 1.

3. Heapify the smaller tree using bottom up construction algorithm.

While constructing heap nodes are attached like this,

Understanding of positions in a tree or a heap is necessary for performing delete operation. Because the key to be deleted is always swapped with last node and the last node is always deleted from heap. Also each time we have to maintain heap property (i.e. parent dominance - parent being greater). Let us understand this delete operation with the help of some example.

Deletion of key 18.

Continuing in this fashion we can perform deletion operation on given heap.

Key Point: Always root's key has to be deleted from a heap.

Analysis

The basic operation in deletion algorithm is the key comparison that should be made to "heapify" the tree after the swap has been made. Each time, after deletion the size of the tree is decreased by 1. It requires less number of key comparisons than twice the heap's height. Therefore time complexity of deletion of O (log n).

Program to perform deletion operation for heap

#include <stdio.h>

#define MAX 50// Max size of Heap

void heapify(int Heap[], int n, int i)

{

int large_ele = i; //get the parent node

int left = 2*i + 2; //access the right child node

int right=2*i + 1; //access the left child node

if( (Heap[left]>Heap[large_ele])&&(left<n))

large_ele left; //larger left child becomes the largest element

if( (Heap[right]>Heap [large_ele])&&(right<n))

large_ele right; //larger right child becomes the largest element

//Swapping in downward direction if the large_ele is not root

if(large_ele != i)

{

int temp =Heap[i];

Heap[i] = Heap[large_ele];

Heap[large_ele] = temp;

heapify(Heap, n, large_ele);

}

}

void Delete(int Heap[], int &n)

{

//get the last element of the heap

int last_element =Heap[n-1];

//replace root with this last element

Heap[0] = last_element;

n = n-1;

//heapify with new root node

heapify(Heap, n, 0);

}

void display(int Heap[], int n)

{

for (int i=

0; i < n; ++i)

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

}

int main()

{

int a[MAX];

int n;

printf("\n Creating a heap");

printf("\nHow many elements are there? ");

scanf("%d", &n);

printf("\n Enter the elements: ");

for(int i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

printf("\n The heap is as follows ...\n");

display(a, n);

Delete(a, n);

printf("\n After deletion the heap is as follows ...\n");

display(a, n);

return 0;

}

Creating a heap

How many elements are there? 7

Enter the elements:

18

12

14

8

7

10

9

The heap is as follows

18 12 14 8 7 10 9

After deletion the heap is as follows...

14 12 10 8 7 9

Ex. 4.15.3 Consider the heap in the following Fig. 4.15.3.

i) Apply deleet operation to the heap.Repair heap after deletion.

ii) Insert 38 into the heap.Repair heap after insertion.

Sol. i) For delete operation we will choose node 40 because this node is of highest priority.

ii) Insert 38: Consider the given heap. After inserting 38, we need to heapify the tree. That means we have to maintain the heap property i.e. parent node must be greater than the child nodes.

Ex. 4.15.4: Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 at a time, into initially empty binary heap. After creating such heap delete the element 8 from heap, how do you repair the heap? Then insert the element in the heap and show the final result (insertion should be at other than lead node).

Sol. : We will create max heap for the set

10 12 1 14 6 5 8 15 3 9 7 4 11 13 2

Review Questions

1. Explain the binary heap operations with examples.

2. Explain the insert and delete operations of heap with examples.