Saturday, 18 July 2015

HeapSort

Heap sort is very easy to implement and its time complexity is O(n log(n)).

Sorting Max-heap:

  1. Let array S is of size n. where  n is no of element to sort
  2. top=n
  3. Pop root from heap and put it at S[top]
  4. top=top-1
  5. heapify(A,1) //Heapify remaining heap again
  6. Repeate step 3 to 5 untill heap is empty


Sorting Min-heap:

  1. Let array S is of size n. where  n is no of element to sort
  2. top=1
  3. Pop root from heap and put it at S[top]
  4. top=top+1
  5. heapify(A,1) //Heapify remaining heap again
  6. Repeate step 3 to 5 untill heap is empty.


C++ Program for HeapSort

  1. //HeapSort
  2. //complexivity O(nlogn)
  3. #include<iostream>
  4. #include<new>
  5. using namespace std;
  6. void BuildHeap(int *heap,int heapSize);
  7. void hepify(int *heap,int i,int heapSize);
  8. void HeapSort(int *heap,int *SortedArray,int &heapSize);
  9. main(){
  10. //initialise array of required heap size
  11.     int heapSize;
  12.     cout<<"Enter max element to sort:- "<<endl;
  13.     cin>>heapSize;
  14.     int *heap;
  15.     heap =new int[heapSize+1];
  16.     heap[0]=0;
  17.     //now insert all element in heap
  18.     //after that we hepify it
  19.     cout<<"Enter element of heap :"<<endl;
  20.     //int a;
  21.     for(int i=1;i<=heapSize;i++){
  22.         cin>>heap[i];
  23.     }
  24.     BuildHeap(heap,heapSize); //make it heap
  25.    
  26.     //Heap Sorting
  27.     int *SortedArray;
  28.     int n;
  29.     n=heapSize;
  30.     SortedArray = new int[heapSize];
  31.     HeapSort(heap,SortedArray,heapSize);
  32.     cout<<\nSorted Data by Heapsort :"<<endl;
  33.     for(int i=0;i<n;i++){
  34.         cout<<SortedArray[i]<<" ";
  35.     }
  36. }
  37. void BuildHeap(int *heap,int heapSize){
  38.      //heapify all node
  39.     for(int i=heapSize/2;i>=1;i--){
  40.         hepify(heap,i,heapSize);
  41.     }
  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;
  54.     //now swap largest with ith node
  55.     if(largest !=i){
  56.         int temp =heap[i];
  57.         heap[i]=heap[largest];
  58.         heap[largest]=temp;
  59.         hepify(heap,largest,heapSize);
  60.     }
  61. }
  62. void HeapSort(int *heap,int *SortedArray,int &heapSize){
  63.     //store root node at end of sorted array
  64.     //change value of root node equal to value of last node of heap
  65.     //then remove heap
  66.     //Again apply BuiltHeap & repeat process until all nodes removed
  67.     if(heapSize>=1){
  68.         SortedArray[heapSize-1]=heap[1];
  69.         heap[1]=heap[heapSize];
  70.         heapSize--; // basically removing last node
  71.        
  72.         hepify(heap,1,heapSize); //again hepify to maintain heap property
  73.         HeapSort(heap,SortedArray,heapSize);
  74.     }
  75. }


Heap Sort

Know More > Heap-basicsHeap Basics Extension - Priority Queue


No comments:

Post a Comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets