Heap Sort

Intuition

This works as follow,

• make a heap using heapify
• pop out the elements and put them at the end of the heap

NOTE: In this code I used extra space for the heap, but I can use heapify on the array also so that no extra space will be required.

#include <bits/stdc++.h>
using namespace std;

void heap_sort(vector<int> &a) {
    /* make a min heap using heapify O(n)*/
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq(std::greater<int>(), a);
    for (int i = 0; i < a.size(); i++) {
        a[i] = pq.top();
        pq.pop();
    }
}

int main() {
    vector<int> a = {1, 4, 2, 5, 5, 6, 3, 3, 4};
    heap_sort(a);
    for (auto i : a) cout << i << " ";
    return 0;
}

Analysis

• Time complexity
  • Best: \(O(n \log(n))\), if the array is sorted
  • Average: \(O(n \log(n))\)
  • Worst: \(O(n \log(n))\)
• Space complexity - \(O(1)\)