C++/Sorting & Searching Programs/Program

Heap Sort

Heap Sort Algorithm in C++ (Complete Implementation)

C++Intermediate
C++
Try
#include <iostream>
using namespace std;

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);
    }
}

void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    printArray(arr, n);
    
    heapSort(arr, n);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}

Output

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

This program teaches you how to implement the Heap Sort algorithm in C++. Heap Sort uses a binary heap data structure to sort elements efficiently. It first builds a max heap from the array, then repeatedly extracts the maximum element and places it at the end. Heap Sort guarantees O(n log n) performance in all cases and sorts in-place.

1. What This Program Does

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.

2. Header File Used

#include <iostream>

This header provides:

  • cout for displaying output
  • cin for taking input from the user

3. 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 2i+1 and 2i+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: 90 /
34 64 / \ /
12 22 25 11

Extract Max (90) → place at end Heapify remaining...

4. 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 2i+1 and 2i+2
  • Heapify ensures this property

5. Function: heapSort()

void heapSort(int arr[], int n) { // Build max heap 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);
}

}

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

6. 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

7. Understanding Binary Heap

Array Representation:

  • Index 0: root
  • Parent at i: children at 2i+1 and 2i+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) ✓

8. 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

9. 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)

10. 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)

11. return 0;

This ends the program successfully.

Summary

  • Heap Sort uses binary heap data structure for sorting.
  • Time complexity: O(n log n) in all cases - guaranteed performance.
  • Space complexity: O(1) - sorts in-place.
  • Not stable - heap operations don't preserve relative order.
  • Builds max heap, then extracts maximum elements repeatedly.
  • Heapify maintains heap property (parent >= children).
  • Understanding binary heaps is essential for Heap Sort.
  • Guaranteed O(n log n) makes it reliable for worst-case scenarios.

This program is fundamental for beginners learning heap data structures, understanding guaranteed performance algorithms, and preparing for priority queues and advanced data structures in C++ programs.

Previous
Quick Sort
Next
Radix Sort