Heap Basics

Heap is also called Left Complete binary tree. i.e Binary tree with some of rightmost node removed.
It is very efficient for priority Queue implementation.

MaxHeap

Heap Type:

1. Minimum Key Heap: Root node is always minimum.
2. Maximum key Heap:  Root node is always maximum.

It can Easily Implement in array and It will be more easier to implement if we take 1th index of array as root of heap( leave 0th index of array ).

Then

• Parent  of i'th Node is = [i/2] {it is flore of i//2}  
• Left child of i'th Node is = 2*i
• Right child of i'th Node = 2*i +1

Heapify(A,i) 

is a function that used to maintain heap property of left complete binary tree.

A <= Array 

i  <= Index of node that need rearrangement to satisfy make array A a heap.

This C++ Program Demonstrate use of Hepify 

1. //Maxheap
2. //Note this program first create complete binary tree then
3. //hepify it . but it does not hepify after each insertion
4. //but it can easily done by applying hepify after each insertion
6. #include<iostream>
7. #include<new>
8. using namespace std;
10. void hepify(int *heap,int i,int heapSize);
11. void Display(int heap[],int heapSize);
14. main(){
15. //initialise array of required heap size
16.     int heapSize;
17.     cout<<"Enter max element in heap :- "<<endl;
18.     cin>>heapSize;
19.     int *heap;
20.     heap =new int[heapSize+1];
21.     heap[0]=0;
22.     //now insert all element in heap
23.     //after that we hepify it
24.     cout<<"Enter element of heap :"<<endl;
25.     //int a;
26.     for(int i=1;i<=heapSize;i++){
27.         cin>>heap[i];
28.     }
29.     cout<<"\nInsert data to form complete binary tree :"<<endl;
30.     //some rightmost child may not present at at last level of heap
31.     Display(heap,heapSize);
32.     // now balance heap
33.     for(int i=heapSize/2;i>=1;i--){
34.         hepify(heap,i,heapSize);
35.     }
36.     //After Balancing Heap
37.     cout<<"\nAfter Balancing Complete binary tree"<<endl;
38.     cout<<"such that it become a heap. ie after heapify :)"<<endl;
39.     Display(heap,heapSize);
42. }
43. void hepify(int *heap,int i,int heapSize){
44.     int left=2*i; //index of left child of ith node
45.     int right=left+1; //index of right child of ith node
46.     int largest;
47.     //find index of largest among (ith node and its left and right child)
48.     if(left<=heapSize && heap[left]>heap[i])
49.         largest=left;
50.     else
51.         largest=i;
52.     if(right<=heapSize && heap[right]>heap[largest])
53.         largest=right;
55.     //now swap largest with ith node
56.     if(largest !=i){
57.         int temp =heap[i];
58.         heap[i]=heap[largest];
59.         heap[largest]=temp;
61.         hepify(heap,largest,heapSize);
62.     }
63. }
65. void Display(int heap[],int heapSize){
66.     cout<<"Heap !!! >>>  ";
67.     for(int i=1;i<=heapSize;i++){
68.         cout<<heap[i]<<" ";
69.     }
70.     cout<<endl;
71. }

Output

Heap Basics Extension - Priority Queue