Heap Sort Algorithm

Description: Heap sort is an in‐place comparison‐based sorting algorithm. It works in two phases:

  1. Build Max‐Heap: View the input array as a binary tree and rearrange it so that it satisfies the max‐heap property: every parent ≥ its children. This can be done by “heapifying” all internal nodes from the bottom up in O(n).
  2. Extract Elements: Repeatedly swap the root (maximum) with the last element of the heap, reduce the heap size by one, and restore the heap property by sift‐down from the root. Each extraction takes O(log n), for total O(n log n).

Time Complexity:

  • Best case: O(n log n)
  • Average case: O(n log n)
  • Worst case: O(n log n)
Space Complexity: O(1) auxiliary (in‐place).

Easy Problems

1. Sort an array of integers

Use heap sort directly to sort any array.

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& A, int n, int i) {
    int largest = i;
    int l = 2*i + 1, r = 2*i + 2;
    if (l < n && A[l] > A[largest]) largest = l;
    if (r < n && A[r] > A[largest]) largest = r;
    if (largest != i) {
        swap(A[i], A[largest]);
        heapify(A, n, largest);
    }
}

void heapSort(vector<int>& A) {
    int n = A.size();
    for (int i = n/2 - 1; i >= 0; --i)
        heapify(A, n, i);
    for (int i = n - 1; i > 0; --i) {
        swap(A[0], A[i]);
        heapify(A, i, 0);
    }
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2};
    heapSort(arr);
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}

2. Find the maximum element

After building a max‐heap, the largest element is at the root A[0].

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& A, int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    if (l < n && A[l] > A[largest]) largest = l;
    if (r < n && A[r] > A[largest]) largest = r;
    if (largest != i) {
        swap(A[i], A[largest]);
        heapify(A, n, largest);
    }
}

int findMax(vector<int> A) {
    int n = A.size();
    for (int i = n/2 - 1; i >= 0; --i)
        heapify(A, n, i);
    return A[0];
}

int main() {
    vector<int> arr = {10, 40, 20, 30};
    cout << "Maximum = " << findMax(arr) << endl;
    return 0;
}

Intermediate Problems

1. Kth Largest Element in an Array

Build a max‐heap, extract the maximum k–1 times; the root is the kth largest.

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& A, int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    if (l < n && A[l] > A[largest]) largest = l;
    if (r < n && A[r] > A[largest]) largest = r;
    if (largest != i) {
        swap(A[i], A[largest]);
        heapify(A, n, largest);
    }
}

int findKthLargest(vector<int> A, int k) {
    int n = A.size();
    for (int i = n/2 - 1; i >= 0; --i)
        heapify(A, n, i);
    for (int i = 0; i < k-1; ++i) {
        swap(A[0], A[n-1-i]);
        heapify(A, n-1-i, 0);
    }
    return A[0];
}

int main() {
    vector<int> arr = {7, 10, 4, 3, 20, 15};
    cout << findKthLargest(arr, 3) << endl; // 3rd largest
    return 0;
}

2. Top K Frequent Elements

Count frequencies, store pairs <element,freq>, then heap‐sort by frequency and take top k.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// reuse heapify from above
void heapify(vector<pair<int,int>>& A, int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    if (l < n && A[l].second > A[largest].second) largest = l;
    if (r < n && A[r].second > A[largest].second) largest = r;
    if (largest != i) {
        swap(A[i], A[largest]);
        heapify(A, n, largest);
    }
}

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;
    vector<pair<int,int>> A(freq.begin(), freq.end());
    int n = A.size();
    for (int i = n/2 - 1; i >= 0; --i)
        heapify(A, n, i);
    vector<int> result;
    for (int i = 0; i < k; ++i) {
        result.push_back(A[0].first);
        swap(A[0], A[n-1-i]);
        heapify(A, n-1-i, 0);
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    auto res = topKFrequent(nums, 2);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Hard Problem

K Closest Points to Origin

Given points (x,y), find k points with smallest Euclidean distance. Use heap sort by distance, then take first k.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point { int x, y; };

void heapify(vector<Point>& A, int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    auto dist = [&](const Point& p){ return p.x*1LL*p.x + p.y*1LL*p.y; };
    if (l < n && dist(A[l]) > dist(A[largest])) largest = l;
    if (r < n && dist(A[r]) > dist(A[largest])) largest = r;
    if (largest != i) {
        swap(A[i], A[largest]);
        heapify(A, n, largest);
    }
}

void heapSortByDist(vector<Point>& A) {
    int n = A.size();
    for (int i = n/2 - 1; i >= 0; --i)
        heapify(A, n, i);
    for (int i = n - 1; i > 0; --i) {
        swap(A[0], A[i]);
        heapify(A, i, 0);
    }
}

vector<Point> kClosest(vector<Point>& points, int k) {
    heapSortByDist(points);
    return vector<Point>(points.begin(), points.begin() + k);
}

int main() {
    vector<Point> pts = {{1,3},{-2,2},{5,8},{0,1}};
    int k = 2;
    auto res = kClosest(pts, k);
    for (auto&p : res) cout << "(" << p.x << "," << p.y << ") ";
    cout << endl;
    return 0;
}