NoteVerse

Heap sort

Comprehensive study notes, diagrams, and exam preparation for Heap sort.

Heap sort

Definition

Heap sort is an efficient comparison-based sorting algorithm that works by first building a max heap for ascending order sorting or a min heap for descending order sorting, and then repeatedly exchanging the root element with the last element of the heap, reducing the heap size, and restoring the heap property until the entire array is sorted.

A heap is a complete binary tree that satisfies the heap property:

  • In a max heap, every parent node is greater than or equal to its children.
  • In a min heap, every parent node is less than or equal to its children.

For ascending order sorting, heap sort usually uses a max heap so that the largest element is always placed at the end of the array first.

Main Content

1. Heap Data Structure

  • A heap is a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right.
  • Heaps are commonly stored in an array, not as linked tree nodes, because the parent-child relationship can be calculated using indices.

For an array indexed from 0:

Parent of node at index i

  • = (i - 1) / 2

Left child of node at index i

  • = 2i + 1

Right child of node at index i

  • = 2i + 2

Example of a max heap:

        50
      /    \
    30      40
   /  \    /  \
 10   5   20   35

Array representation:

[50, 30, 40, 10, 5, 20, 35]

This structure ensures that the largest element is always at the root in a max heap, which is why heap sort can efficiently extract the maximum repeatedly.

2. Heap Property and Heapification

  • The heap property is the rule that maintains order inside the heap:
  • In a max heap, each parent must be greater than or equal to its children.
  • In a min heap, each parent must be less than or equal to its children.

Heapification

  • is the process of converting a subtree or an entire array into a heap by fixing violations of the heap property.

There are two important forms of heapification:

1. Build heap

Converts an unsorted array into a valid heap.

2. Restore heap after deletion/extraction

After removing the root, the heap property may be broken, so heapification is used again to repair it.

Example: If the array is:

[4, 10, 3, 5, 1]

To build a max heap, the array becomes:

[10, 5, 3, 4, 1]

Heapification is crucial because heap sort depends on it at two stages:

  • building the initial heap
  • reordering the remaining elements after each extraction

Without heapification, the sorting process would not preserve the correct order structure.

3. Sorting Mechanism of Heap Sort

  • Heap sort usually sorts in ascending order by using a max heap.
  • The largest value is moved to the end of the array, then the heap size is reduced by one, and the heap is restored.

The process works like this:

  1. Build a max heap from the input array.
  2. Swap the root element with the last element in the heap.
  3. Reduce the heap size by 1, effectively fixing the largest element in its final position.
  4. Heapify the root again to restore max heap structure.
  5. Repeat until the heap size becomes 1.

Example: Initial array:

[4, 10, 3, 5, 1]

After building max heap:

[10, 5, 3, 4, 1]

Then:

  • Swap 10 and 1 → [1, 5, 3, 4, 10]
  • Heapify remaining heap → [5, 4, 3, 1, 10]
  • Swap 5 and 1 → [1, 4, 3, 5, 10]
  • Heapify remaining heap → [4, 1, 3, 5, 10]
  • Continue until sorted

Final sorted array:

[1, 3, 4, 5, 10]

This method ensures that each largest element moves to its correct position from the end of the array toward the beginning.

Working / Process

1. Build the heap

  • Start with the unsorted array.
  • Convert it into a max heap for ascending order.
  • This is done by applying heapify from the last non-leaf node up to the root.
  • After this step, the root contains the largest element.

2. Remove the root and place it at the end

  • Swap the root element with the last element in the heap.
  • The largest element is now in its final sorted position.
  • Decrease the heap size by one so the sorted part is excluded from future heap operations.

3. Restore the heap and repeat

  • Apply heapify to the root again to restore the max heap property.
  • Repeat the swap-and-heapify process until all elements are sorted.
  • The array becomes sorted in ascending order.

Example using the array [6, 3, 8, 2, 5, 1]:

  • Build max heap: [8, 5, 6, 2, 3, 1]
  • Swap root and last: [1, 5, 6, 2, 3, 8]
  • Heapify first five elements: [6, 5, 1, 2, 3, 8]
  • Swap again: [3, 5, 1, 2, 6, 8]
  • Heapify: [5, 3, 1, 2, 6, 8]

Continue until sorted: [1, 2, 3, 5, 6, 8]

A useful way to visualize the process is:

Initial array  -> Build max heap -> Repeated root swap + heapify -> Sorted array

This shows that heap sort is essentially a repeated extraction of the largest element from a heap.

Advantages / Applications

Guaranteed time complexity of O(n log n)

Heap sort performs efficiently in the best, average, and worst cases, making it reliable for large datasets.

In-place sorting

It requires only constant extra memory, so it is memory-efficient compared to algorithms like merge sort that need additional arrays.

Useful in priority-based systems and real-world applications

The heap structure is useful in CPU scheduling, event simulation, graph algorithms like Dijkstra’s algorithm, and implementing priority queues. Heap sort is also used when a predictable worst-case performance is needed.

Summary

  • Heap sort is a comparison-based sorting method based on a binary heap.
  • It builds a max heap and repeatedly moves the largest element to the end.
  • It is efficient, in-place, and has O(n log n) performance.
  • Important terms to remember: heap, max heap, min heap, heapify, root, parent, child, complete binary tree
← Prev: Selection sort
Next: Insertion sort →