Binary Heap
We will discuss the following topics in this blog:
Introduction to Heap
Array representation of Heap
Insertion in Heap
Deletion from Heap
Priority Queue
Introduction To Heap :
Let’s understand the concept of heap with this example. Why do you think the host are not in a mood to invite the guest to christmas party from next year onwards….?
Think about it...Now let’s move towards the topic.
Heap is a data structure that satisfy the property of complete binary tree. It is also called as binary heap.
A complete binary tree is a tree in which:
1.Every level, except possibly the last, is filled
2.All the nodes are as far left as possible
I hope you can now relate this with the picture shown above...the host doesn’t appreciate the presence of that guest because neither the tree nor the presents form a complete binary tree (binary heap) :)
Viewing a heap as a tree, we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf, and we define the height of heap to be the height of it’s root. Since, a heap of n elements is based on complete binary tree ,it’s height is O(logn).
Max Heap Property: Every node should have an element greater than or equal to it’s descendants with maximum valued element at the root. Thus, allowing duplicates.
Min Heap Property: Every node should have an element smaller than or equal to it’s descendants with minimum valued element at the root. Thus, allowing duplicates.
Array Representation of Heap:
Root of tree is A[1]
Left child of A[i] = A[2i]
Right child of A[i] = A[2i + 1]
Parent of A[i] = A[ i/2]
Insertion in Heap:
1. Insert the element in an array at the next free space i.e. at the end. In order to maintain a complete binary tree.
2. Compare the inserted element with it’s parent .
3.If the parent element is smaller than the inserted element than swap the elements (min heap)
4.Repeat step 2 and 3 until the heap property is satisfied.
Pseudo code:
void insert(int A[],int n);
{
int temp,i=n;
temp=A[n]; //assigning the last element in a variable
while(i>1 && temp<A[i/2]) //checking the element with it’s parent
{
A[i]=A[i/2]; //swapping the two elements
i=i/2;
}
A[i]=temp;
}
Deletion from Heap:
1.Remove the root element.
2.Make last element the root element.
3.Compare the children of new root ,if the root element is greater than any of it’s child then swap it with the smallest child.(min heap)
4. Repeat step 3 until the heap property is satisfied
Pseudo code:
void delete(int A[],int n)
{
int x,i,j;
x=A[n];
A[i]=A[n];//making last element the root element
i=1;j=2*i;//j is the left child
while(j<n-1)
{
if(j<n-1)
{
if(A[j+1]<A[j])//compare right child and left child
{j=j+1;}
if(A[i]>A[j]) //parent element is greater than the child element
{swap(A[i],A[j]);//swap
i=j;
j=2*j;
}
else
break;
}
A[n]=x;
}
Time and Space Complexity:
Space O(n)
Search O(n)
Insert O(log n)
Delete O(log n)
Binary Heap as Priority Queue:
In a priority queue the logical order of items inside a queue is determined by their “priority”. Specifically, the highest priority items are retrieved from the queue ahead of lower priority items.
The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us to enqueue or dequeue items in O(logn).
Following are important points of binary heap as a priority queue:
Each element is associated with a value
- The key with highest priority will be extracted first
- There are two types of priority queue:-
· MAX-PRIORITY QUEUE- max element is extracted
· MIN-PRIORITY QUEUE — min element is extracted
- Operation on priority queue
- MAX- priority queue support following operation:-
- INSERT(S, x): inserts element x into set S
- EXTRACT-MAX(S): removes and returns element of S with largest key
- MAXIMUM(S): returns element of S with largest key
- INCREASE-KEY(S, x, k): increases value of element x’s key to k (Assume k ≥ x’s current key value)
Thank you for reading !
