Saturday, 18 July 2015

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. }

No comments:

Post a Comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets