Heap Sort

In the previous lesson, we learned about Quick Sort, a fast and widely used sorting algorithm.

Quick Sort is excellent in practice, but its performance depends on good pivot selection.

In this lesson, we study another powerful sorting algorithm that guarantees good performance: Heap Sort.

Heap Sort combines binary heap data structures with sorting logic to achieve efficient and reliable results.

The Core Idea Behind Heap Sort

Heap Sort is based on a special tree-based structure called a heap.

A heap is a complete binary tree that satisfies a specific ordering rule.

In a max heap, the largest element is always at the root.

Heap Sort repeatedly removes the largest element and places it at the end of the array.

What Is a Binary Heap?

A binary heap has two important properties:

First, it is a complete binary tree, meaning all levels are filled except possibly the last.

Second, it follows the heap property:

• In a max heap, parent ≥ children
• In a min heap, parent ≤ children

Heap Sort usually uses a max heap.

Steps of Heap Sort

Heap Sort works in two main phases.

In the first phase, the array is converted into a max heap.

In the second phase, the root element (largest value) is swapped with the last element, and the heap size is reduced.

This process continues until the array becomes fully sorted.

Heap Sort Algorithm (Code)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    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[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)

This implementation sorts the array in place without using extra memory.

Time and Space Complexity

Best, Average, and Worst Case Time Complexity: O(n log n)

Unlike Quick Sort, Heap Sort never degrades to O(n²).

Space Complexity: O(1) (extra space), making it memory efficient.

Heap Sort vs Quick Sort

Heap Sort provides guaranteed performance, while Quick Sort is faster on average.

Heap Sort is preferred when:

Predictable performance and low memory usage are required.

Quick Sort is preferred when:

Average-case speed is more important than worst-case guarantees.

Real-World Usage

Heap Sort is used in systems where worst-case performance must be tightly controlled.

It is also useful when working with large datasets and limited memory.

Mini Practice

Think carefully:

• Why does Heap Sort always guarantee O(n log n)?
• Why is Heap Sort not considered stable?

Exercises

Quick Quiz

In the next lesson, we will explore Counting Sort and Radix Sort and see how non-comparison-based sorting can achieve linear time performance.