Heap sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to the selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining element.
Implementation:
CPP
// C++ program for implementation of Heap Sort#include <iostream>using namespace std;Â
// To heapify a subtree rooted with node i which is// an index in arr[]. n is size of heapvoid heapify(int arr[], int n, int i){    int largest = i; // Initialize largest as root Since we are using 0 based indexing    int l = 2 * i + 1; // left = 2*i + 1    int r = 2 * i + 2; // right = 2*i + 2Â
    // If left child is larger than root    if (l < n && arr[l] > arr[largest])        largest = l;Â
    // If right child is larger than largest so far    if (r < n && arr[r] > arr[largest])        largest = r;Â
    // If largest is not root    if (largest != i) {        swap(arr[i], arr[largest]);Â
        // Recursively heapify the affected sub-tree        heapify(arr, n, largest);    }}Â
// main function to do heap sortvoid heapSort(int arr[], int n){Â Â Â Â // Build heap (rearrange array)Â Â Â Â for (int i = n / 2 - 1; i >= 0; i--)Â Â Â Â Â Â Â Â heapify(arr, n, i);Â
    // One by one extract an element from heap    for (int i = n - 1; i >= 0; i--) {        // Move current root to end        swap(arr[0], arr[i]);Â
        // call max heapify on the reduced heap        heapify(arr, i, 0);    }}Â
/* A utility function to print array of size n */void printArray(int arr[], int n){Â Â Â Â for (int i = 0; i < n; ++i)Â Â Â Â Â Â Â Â cout << arr[i] << " ";Â Â Â Â cout << "\n";}Â
// Driver programint main(){    int arr[] = { 60 ,20 ,40 ,70, 30, 10};    int n = sizeof(arr) / sizeof(arr[0]);  //heapify algorithm  // the loop must go reverse you will get after analyzing manually   // (i=n/2 -1) because other nodes/ ele's are leaf nodes   // (i=n/2 -1) for 0 based indexing  // (i=n/2) for 1 based indexing     for(int i=n/2 -1;i>=0;i--){       heapify(arr,n,i);   }     cout << "After heapifying array is \n";    printArray(arr, n);          heapSort(arr, n);Â
    cout << "Sorted array is \n";    printArray(arr, n);       return 0;}//code by Prajwal Chougale |
Output
After heapifying array is 70 60 40 20 30 10 Sorted array is 10 20 30 40 60 70
Time complexity : O(N*logN)
Auxiliary space: O(1)
Approach Name: Heap Sort (Using STL)
Steps:
- Convert the input array to a vector.
- Convert the vector into a Max Heap using the make_heap function of the STL.
- Sort the Max Heap using the sort_heap function of the STL.
C++
#include <algorithm>#include <iostream>#include <vector>using namespace std;Â
void heapSort(int arr[], int n){    // Convert array to vector    vector<int> v(arr, arr + n);Â
    // Convert vector to Max Heap    make_heap(v.begin(), v.end());Â
    // Sort Max Heap    sort_heap(v.begin(), v.end());Â
    // Copy sorted vector back to array    copy(v.begin(), v.end(), arr);}Â
int main(){Â Â Â Â int arr[] = { 60, 20, 40, 70, 30, 10 };Â Â Â Â int n = sizeof(arr) / sizeof(arr[0]);Â
    heapSort(arr, n);Â
    cout << "Sorted array is \n";    for (int i = 0; i < n; ++i)        cout << arr[i] << " ";    cout << endl;} |
Output
Sorted array is 10 20 30 40 60 70
Time Complexity: O(n*log(n)) in all cases.
Auxiliary Space: O(1) in-place sorting algorithm.
Please refer complete article on Heap Sort for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
