Heap Sort in C++

Heap Sort Algorithm in C++ (Complete Implementation).

IntermediateSorting & Searching ProgramsExample 6 of 13

heap-sort.cpp

1#include <iostream>
2using namespace std;
3
4void heapify(int arr[], int n, int i) {
5    int largest = i;
6    int left = 2 * i + 1;
7    int right = 2 * i + 2;
8    
9    if (left < n && arr[left] > arr[largest])
10        largest = left;
11    
12    if (right < n && arr[right] > arr[largest])
13        largest = right;
14    
15    if (largest != i) {
16        swap(arr[i], arr[largest]);
17        heapify(arr, n, largest);
18    }
19}
20
21void heapSort(int arr[], int n) {
22    // Build max heap
23    for (int i = n / 2 - 1; i >= 0; i--)
24        heapify(arr, n, i);
25    
26    // Extract elements from heap one by one
27    for (int i = n - 1; i > 0; i--) {
28        swap(arr[0], arr[i]);
29        heapify(arr, i, 0);
30    }
31}
32
33void printArray(int arr[], int n) {
34    for (int i = 0; i < n; i++) {
35        cout << arr[i] << " ";
36    }
37    cout << endl;
38}
39
40int main() {
41    int arr[] = {64, 34, 25, 12, 22, 11, 90};
42    int n = sizeof(arr) / sizeof(arr[0]);
43    
44    cout << "Original array: ";
45    printArray(arr, n);
46    
47    heapSort(arr, n);
48    
49    cout << "Sorted array: ";
50    printArray(arr, n);
51    
52    return 0;
53}

Output

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

What's going on

The program sorts an array of integers using the Heap Sort algorithm. For example:

Input array: [64, 34, 25, 12, 22, 11, 90]

Output array: [11, 12, 22, 25, 34, 64, 90]

Heap Sort works by treating the array as a binary heap, building a max heap, and then repeatedly extracting the maximum element to build the sorted array from the end.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Heap Sort

Binary Heap Concept

Complete binary tree stored in array

Max Heap: parent >= children (root is maximum)

Array representation: parent at i, children at 2*i+1 and 2*i+2

Algorithm Steps

1.Build max heap from array

2.Swap root (max) with last element

3.Reduce heap size and heapify root

4.Repeat until heap is empty

Visual Example

Array: [64, 34, 25, 12, 22, 11, 90]

Build Max Heap:

/ \

34 64

/ \ / \

12 22 25 11

Extract Max (90) → place at end

Heapify remaining...

Function: heapify()

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(arr[i], arr[largest]);

heapify(arr, n, largest);

}

How it works

Maintains max heap property at node i

Finds largest among node i and its children

If largest is not i, swap and recursively heapify

Ensures parent >= children

Heap Property

For max heap: arr[parent] >= arr[child]

Parent at index i, children at 2*i+1 and 2*i+2

Heapify ensures this property

Function: heapSort()

void heapSort(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// Extract elements from heap

for (int i = n - 1; i > 0; i--) {

swap(arr[0], arr[i]);

heapify(arr, i, 0);

}

1// Build max heap

How it works

Build Heap

: Start from last non-leaf node (n/2 - 1), heapify upward

Extract

: Swap root (max) with last element, reduce heap size

Heapify

: Restore heap property after swap

Repeat until all elements extracted

Step-by-Step Algorithm

Step 1: Build Max Heap

Start from last non-leaf node: n/2 - 1

Heapify each node upward

Result: max heap with largest at root

Step 2: Extract Maximum

Swap arr[0] (root/max) with arr[n-1] (last)

Largest element now at end (sorted position)

Reduce heap size: n - 1

Step 3: Restore Heap

Heapify root to restore max heap property

New maximum at root

Step 4: Repeat

Continue extracting and heapifying

Sorted portion grows from end

Heap shrinks from end

Understanding Binary Heap

Array Representation

Index 0: root

Parent at i: children at 2*i+1 and 2*i+2

Child at i: parent at (i-1)/2

Example

(array indices):

Array: [90, 34, 64, 12, 22, 25, 11]

0 1 2 3 4 5 6

Tree:

0(90)

/ \

1(34) 2(64)

/ \ / \

3(12) 4(22) 5(25) 6(11)

Heap Property

Parent (90) >= children (34, 64) ✓

Parent (34) >= children (12, 22) ✓

Parent (64) >= children (25, 11) ✓

Time and Space Complexity

Time Complexity

: O(n log n) in all cases

Build heap: O(n) - bottom-up approach

Extract n elements: O(n log n) - each extraction is O(log n)

Total: O(n log n) - guaranteed performance

Space Complexity

: O(1)

Sorts in-place (modifies original array)

Only uses constant extra space

No additional arrays needed

Stability

: Not Stable

Swapping during heapify can change relative order

Heap operations don't preserve stability

When to Use Heap Sort

Best For

When guaranteed O(n log n) is required

When in-place sorting is needed

When worst-case performance matters

Priority queue applications

Not Recommended For

When stability is required

Small datasets (overhead of heap operations)

When average-case performance is more important (Quick Sort better)

Cache performance sensitive (poor cache locality)

Important Considerations

Building Heap

Start from n/2 - 1 (last non-leaf node)

Heapify upward ensures correct heap

Bottom-up approach is O(n), not O(n log n)

Heap Size

Decreases with each extraction

Heap portion: [0, i-1]

Sorted portion: [i, n-1]

Heapify Direction

During build: bottom-up (from n/2-1 to 0)

During extraction: top-down (from root)

return 0;

This ends the program successfully.

PreviousQuick Sort NextRadix Sort