Heap Data Structure

Heap Data Structure

Heap data structure is a specialized binary tree based data structure. Heap is a binary tree with special characteristics. In a heap data structure nodes are arranged based on their value. A heap data structure . SOme time called as Binary Heap.

There are two types of heap data structure and they are follows

1. Max Heap
2. Min Heap

1. Min Heap

The value of the parent node must be less than or equal to of its children.

The min-heap is defined as, for every node i, the value of node i is greater than or equal to its parent value except the root node. Mathematically, it can be defined as:

A[Parent(i)] <= A[i]

2. Max Heap

Max heap data structure is a specialized full binary tree data structure except last leaf node can be alone. In max heap nodes are arranged based on node value. Max heap is defined as

It is full binary tree in which every parent node contains greater or equal value than its child nodes. And last node can be alone.

A[Parent(i)] >= A[i]

Algorithm of insert operation in the max heap.

insertHeap(A, n, value)  
{  
n=n+1; 
A[n]=value; 
i = n;    
while(i>1)   
{  
parent= floor value of i/2;
if(A[parent]<A[i])   
{  
swap(A[parent], A[i]);  
i = parent;  
}  
else  
{  
return;  
}  
}  
}

Insertion in the Heap tree

44, 33, 77, 11, 55, 88, 66

To create the max heap tree,

We have to insert the element in such a way that the property of the complete binary tree must be maintained.

The value of the parent node must be greater than the  child.

Step 1: Firstly we add the 44 element in the tree.

Step 2: The next element is 33. The insertion in the binary tree starts from the left side so 44 will be added at the left of 33 as shown below figure

Step 3: The next element is 77 and it will be added to the right of the 44 as shown below figure

Here parent node 44 is less than the child 77. So, we will swap these two values as shown below figure

Step 4: The next element is 11. The node 11 is added to the left of 33 as shown below  figure

Step 5: The next element is 55. To make complete binary tree, we will add the  55 node  to the right of 33 as shown below figure

As we can observe in the above figure that it does not satisfy the max heap property because 33<55, so we will swap two values as shown below figure

Step 6: The next element is 88. The left subtree is completed so we will add 88 to the left of 44 as shown below figure

Deletion in Heap Tree

In Deletion in the heap tree, the root node is always deleted and it is replaced with the last element.

Algorithm to heapify the tree

MaxHeapify(A, n, i)  
{  
int largest =i;  
int l= 2i;  
int r= 2i+1;  
while(l<=n && A[l]>A[largest])  
{  
largest=l;  
}  
while(r<=n && A[r]>A[largest])  
{  
largest=r;  
}   
if(largest!=i)  
{  
swap(A[largest], A[i]);  
heapify(A, n, largest);  
}}