Heap Basics Extension - Priority Queue

Priority Queue is very commonly used in operating system to schedule task, priority Queue can very easily and very effectively can implement in Heap.

Insert A new Key in Heap :

Start from end of heap and find appropriate position then insert.

---

Heap-Insert(A,key)

1. Heap-Size[A] <- Heap-Size[A]+1
2. i=Heap-Size[A]
3. while(i>1 and A[parant(i)]<key)
• A[i]<-A[Parant(i)]
• i=Parent(i)
4. A[i]=Key

---

Note: If We remove root node then to hepify again we just have to call heapify(A,1)

See Carefully these algorithm in below program

• Insert New Element in heap => Heap-Insert(A,key)
• Extract max from maxHeap => Heap-Max-Extract(A)
• Delete I'th node from Heap => Heap-Delete(A,i) 

Priority Queue Implementation in Heap (C++ )

1. //Priority Queue implementation in heap
2.  
3. #include<iostream>
4. #include<new>
5. using namespace std;
6.  
7. void heapify(int *heap,int i,int heapSize);
8. int Heap_Extraxt_max(int *heap,int &heapsize);
9. void Heap_Insert(int *heap,int &heapsize,int key);
10. void Heap_Delete(int *heap,int i,int &heapsize);
11. void Heap_Display(int *heap, int &heapsize);
12.  
13. main(){
14. //initialise array of required heap size
15.     int heapSize;
16.     cout<<"Enter max element of heap:_ "<<endl;
17.     cin>>heapSize;
18.     int *heap;
19.     heap =new int[heapSize+10];
20.     heap[0]=0;
21.     //now insert all element in heap
22.     //after that we hepify it
23.     cout<<"Enter element of heap :"<<endl;
24.     int key,j;
25.     for(int i=1;i<=heapSize;i++){
26.         cin>>key;
27.         j=i-1;
28.         Heap_Insert(heap,j,key);
29.     }
30.     Heap_Display(heap,heapSize);
31.  
32.     //max extraction
33.     cout<<"Max Extraction :"<<Heap_Extraxt_max(heap,heapSize)<<endl;
34.     cout<<"Max Extraction :"<<Heap_Extraxt_max(heap,heapSize)<<endl;
35.     Heap_Display(heap,heapSize);
36.    
37.         //Delete Ith node
38.         cout<<"Delete 2nd node :"<<endl;
39.         Heap_Delete(heap,2,heapSize);
40.        
41.         cout<<"Delete 10th node :"<<endl;
42.         Heap_Delete(heap,10,heapSize);
43.         Heap_Display(heap,heapSize);
44.        
45.        
46.        
47. }
48.  
49. void Heap_Insert(int *heap,int &heapsize,int key){
50.         heapsize=heapsize+1;
51.         int i= heapsize;
52.         while(i>1 && key>heap[i/2]){
53.                 heap[i]=heap[i/2];
54.                 i=i/2;
55.         }
56.         heap[i]=key;
57. }
58.  
59. void heapify(int *heap,int i,int heapSize){
60.     int left=2*i; //index of left child of ith node
61.     int right=left+1; //index of right child of ith node
62.     int largest;
63.     //find index of largest among (ith node and its left and right child)
64.     if(left<=heapSize && heap[left]>heap[i])
65.         largest=left;
66.     else
67.         largest=i;
68.     if(right<=heapSize && heap[right]>heap[largest])
69.         largest=right;
70.  
71.     //now swap largest with ith node
72.     if(largest !=i){
73.         int temp =heap[i];
74.         heap[i]=heap[largest];
75.         heap[largest]=temp;
76.  
77.         heapify(heap,largest,heapSize);
78.     }
79. }
80.  
81. int Heap_Extraxt_max(int *heap,int &heapsize){
82.         if(heapsize<1){
83.                 cout<<"Underflow Condition"<<endl;
84.                 return -1;
85.         }
86.         else{
87.                 int max=heap[1];
88.                 heap[1]=heap[heapsize];
89.                 heapsize--;
90.                 heapify(heap,1,heapsize);
91.                 return max;
92.         }
93. }
94.  
95. void Heap_Delete(int *heap,int i,int &heapsize){
96.         if(heapsize<i){
97.                 cout<<"Index Overflow "<<endl;
98.         }
99.         else{
100.                 if(heapsize != i){
101.                         heap[i]=heap[heapsize];
102.                         heapsize--;
103.                         heapify(heap,i,heapsize);
104.                 }
105.                 else
106.                         heapsize--;
107.         }
108. }
109. void Heap_Display(int *heap, int &heapsize){
110.         cout<<"\n\n Heap Status :"<<endl;
111.         for(int i=1;i<=heapsize;i++){
112.                 cout<<heap[i]<<", ";
113.         }
114.         cout<<endl;
115. }