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;
7. void BuildHeap(int *heap,int heapSize);
8. void hepify(int *heap,int i,int heapSize);
9. void HeapSort(int *heap,int *SortedArray,int &heapSize);
11. main(){
12. //initialise array of required heap size
13.     int heapSize;
14.     cout<<"Enter max element to sort:- "<<endl;
15.     cin>>heapSize;
16.     int *heap;
17.     heap =new int[heapSize+1];
18.     heap[0]=0;
19.     //now insert all element in heap
20.     //after that we hepify it
21.     cout<<"Enter element of heap :"<<endl;
22.     //int a;
23.     for(int i=1;i<=heapSize;i++){
24.         cin>>heap[i];
25.     }
26.     BuildHeap(heap,heapSize); //make it heap
27.    
28.     //Heap Sorting
29.     int *SortedArray;
30.     int n;
31.     n=heapSize;
32.     SortedArray = new int[heapSize];
33.     HeapSort(heap,SortedArray,heapSize);
34.     cout<<" \nSorted Data by Heapsort :"<<endl;
35.     for(int i=0;i<n;i++){
36.         cout<<SortedArray[i]<<" ";
37.     }
39. }
40. void BuildHeap(int *heap,int heapSize){
41.      //heapify all node
42.     for(int i=heapSize/2;i>=1;i--){
43.         hepify(heap,i,heapSize);
44.     }
45. }
46. void hepify(int *heap,int i,int heapSize){
47.     int left=2*i; //index of left child of ith node
48.     int right=left+1; //index of right child of ith node
49.     int largest;
50.     //find index of largest among (ith node and its left and right child)
51.     if(left<=heapSize && heap[left]>heap[i])
52.         largest=left;
53.     else
54.         largest=i;
55.     if(right<=heapSize && heap[right]>heap[largest])
56.         largest=right;
58.     //now swap largest with ith node
59.     if(largest !=i){
60.         int temp =heap[i];
61.         heap[i]=heap[largest];
62.         heap[largest]=temp;
64.         hepify(heap,largest,heapSize);
65.     }
66. }
67. void HeapSort(int *heap,int *SortedArray,int &heapSize){
68.     //store root node at end of sorted array
69.     //change value of root node equal to value of last node of heap
70.     //then remove heap
71.     //Again apply BuiltHeap & repeat process until all nodes removed
72.     if(heapSize>=1){
73.         SortedArray[heapSize-1]=heap[1];
74.         heap[1]=heap[heapSize];
75.         heapSize--; // basically removing last node
76.        
77.         hepify(heap,1,heapSize); //again hepify to maintain heap property
78.         HeapSort(heap,SortedArray,heapSize);
79.     }
80. }
81. 
    

Heap Sort

Know More > Heap-basics, Heap Basics Extension - Priority Queue