← Back to DSA Course | Chapter 12: Heaps | Lesson 3 of 5

Heap Sort

In this page:

  1. Heap Sort Idea
  2. Build Max Heap
  3. Move Maximum
  4. Complexity
  5. Practice

Heap Sort Idea

Heap sort works in two phases: first it rearranges the input array into a valid max heap, and then it repeatedly extracts the maximum value from the heap's root and places it at the end of the array, shrinking the heap by one each time.

Example: Heap Sort Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {4,10,3,5,1};
    cout << "Phase 1: build max heap. Phase 2: repeatedly extract max to the end" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Phase 1: build max heap. Phase 2: repeatedly extract max to the end");
    }
}
print("Phase 1: build max heap. Phase 2: repeatedly extract max to the end")
#include <stdio.h>
int main() {
    printf("Phase 1: build max heap. Phase 2: repeatedly extract max to the end\n");
    return 0;
}

Build Max Heap

Building the max heap starts from the last non-leaf node and works backward toward the root, sifting each node down into its correct position — this bottom-up approach builds the full heap property in linear time rather than inserting elements one at a time.

Example: Build Max Heap

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
int main() {
    int arr[] = {4,10,3,5,1}, n = 5;
    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
    cout << "Max heap built, root=" << arr[0] << endl;
    return 0;
}
public class Main {
    static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) { int t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
    }
    public static void main(String[] args) {
        int[] arr = {4,10,3,5,1};
        for (int i = arr.length/2 - 1; i >= 0; i--) heapify(arr, arr.length, i);
        System.out.println("Max heap built, root=" + arr[0]);
    }
}
def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [4, 10, 3, 5, 1]
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)
print("Max heap built, root=", arr[0])
#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2, t;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
}
int main() {
    int arr[] = {4,10,3,5,1}, n = 5;
    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
    printf("Max heap built, root=%d\n", arr[0]);
    return 0;
}

Move Maximum

Since the root of a max heap always holds the current largest value, extraction swaps the root with the last element of the still-unsorted portion, shrinks the heap by one, and then sifts the new root down to restore the heap property before repeating.

Example: Move Maximum

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
int main() {
    int arr[] = {10,5,3,4,1}, n = 5;
    swap(arr[0], arr[n-1]);
    heapify(arr, n-1, 0);
    cout << "Max moved to end, arr[4]=" << arr[4] << " new root=" << arr[0] << endl;
    return 0;
}
public class Main {
    static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) { int t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
    }
    public static void main(String[] args) {
        int[] arr = {10,5,3,4,1};
        int n = arr.length;
        int t = arr[0]; arr[0] = arr[n-1]; arr[n-1] = t;
        heapify(arr, n-1, 0);
        System.out.println("Max moved to end, arr[4]=" + arr[4] + " new root=" + arr[0]);
    }
}
def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [10, 5, 3, 4, 1]
n = len(arr)
arr[0], arr[n-1] = arr[n-1], arr[0]
heapify(arr, n - 1, 0)
print("Max moved to end, arr[4]=", arr[4], "new root=", arr[0])
#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2, t;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
}
int main() {
    int arr[] = {10,5,3,4,1}, n = 5, t;
    t = arr[0]; arr[0] = arr[n-1]; arr[n-1] = t;
    heapify(arr, n-1, 0);
    printf("Max moved to end, arr[4]=%d new root=%d\n", arr[4], arr[0]);
    return 0;
}

Complexity

Because both heap construction and repeated extraction happen entirely within the original array — no separate output array is needed — heap sort runs using only O(1) extra space beyond the input itself, on top of its O(n log n) time.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
    cout << "Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array");
    }
}
print("Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array")
#include <stdio.h>
int main() {
    printf("Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array\n");
    return 0;
}

Practice

Trace heap sort on a small array like [4, 10, 3, 5, 1]: build the initial max heap, then watch each extraction move the current maximum to its final sorted position at the end while the heap shrinks from the front.

Example: Practice

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
void heapSort(int arr[], int n) {
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); }
}
int main() {
    int arr[] = {4,10,3,5,1};
    heapSort(arr, 5);
    for (int v : arr) cout << v << " ";
    return 0;
}
public class Main {
    static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) { int t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
    }
    public static void main(String[] args) {
        int[] arr = {4,10,3,5,1};
        int n = arr.length;
        for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
        for (int i = n-1; i > 0; i--) { int t=arr[0]; arr[0]=arr[i]; arr[i]=t; heapify(arr, i, 0); }
        for (int v : arr) System.out.print(v + " ");
    }
}
def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [4, 10, 3, 5, 1]
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)
for i in range(n - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)
print(arr)
#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2, t;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
}
int main() {
    int arr[] = {4,10,3,5,1}, n = 5, t;
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) { t=arr[0]; arr[0]=arr[i]; arr[i]=t; heapify(arr, i, 0); }
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Min Heap and Max Heap Next Lesson → K Largest Elements

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.