Heap Sort Algorithm Overview

👋 Welcome Gophers! In this lesson, we are going to explore how the heap sort algorithm works and understand the heap data structure that powers it.

What is a Heap?

A heap is a specialized tree-based data structure 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 sorting purposes, we typically use a max-heap. Here’s a visual example of a max-heap:

      10
    /    \
   9      7
  / \    / \
 8   4  6   3

In this heap, 10 is the largest element, and it sits at the root. This is important because heap sort repeatedly extracts the maximum element and places it at the end of the array.

How Heap Sort Works

Heap sort works in two phases:

Build Phase: Convert the input array into a max-heap
Extraction Phase: Repeatedly extract the maximum element (root) and place it at the end of the sorted array

Here’s the process step by step:

Build a max-heap from the input array
Swap the root (maximum element) with the last element in the heap
Remove the last element from the heap (it’s now in the correct sorted position)
Restore the heap property by “heapifying” the root
Repeat steps 2-4 until only one element remains

Heapify Operation

The heapify operation maintains the max-heap property. When we remove the root, we place the last element at the root and then move it down the tree, swapping it with its larger child until the heap property is restored.

For example, if we have this heap and remove the root:

Before removal:     After removal + restore:
     10                    9
    /  \                  /  \
   9    7        -->     8    7
  / \  / \              / \
 8   4 6  3            4   3

The element 3 is moved to the root, then swapped down with 9 to restore the max-heap property.

Time and Space Complexity

Best Case: O(n log n) - even on already sorted data
Average Case: O(n log n) - consistent performance
Worst Case: O(n log n) - guaranteed performance
Space Complexity: O(1) - sorts in place with no extra space!

Heap sort achieves the same O(n log n) performance as merge sort but with only O(1) space, making it excellent for memory-constrained environments.

Visual Representation

Here’s a visual representation of a max-heap structure and how heapify works:

<svg viewBox="0 0 700 500" xmlns="http://www.w3.org/2000/svg" style="background-color: #1a1a1a; font-family: monospace;">
  <!-- Title -->
  <text x="350" y="25" fill="#e0e0e0" font-size="16" text-anchor="middle" font-weight="bold">Max-Heap Structure</text>

  <!-- Root -->
  <circle cx="350" cy="60" r="25" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
  <text x="350" y="68" fill="#000" text-anchor="middle" font-size="16" font-weight="bold">10</text>

  <!-- First level connections -->
  <line x1="350" y1="85" x2="250" y2="125" stroke="#666" stroke-width="2"/>
  <line x1="350" y1="85" x2="450" y2="125" stroke="#666" stroke-width="2"/>

  <!-- Level 1 nodes -->
  <circle cx="250" cy="150" r="25" fill="#4169e1" stroke="#4169e1" stroke-width="2"/>
  <text x="250" y="158" fill="#fff" text-anchor="middle" font-size="16" font-weight="bold">9</text>

  <circle cx="450" cy="150" r="25" fill="#4169e1" stroke="#4169e1" stroke-width="2"/>
  <text x="450" y="158" fill="#fff" text-anchor="middle" font-size="16" font-weight="bold">7</text>

  <!-- Second level connections -->
  <line x1="250" y1="175" x2="180" y2="215" stroke="#666" stroke-width="2"/>
  <line x1="250" y1="175" x2="320" y2="215" stroke="#666" stroke-width="2"/>
  <line x1="450" y1="175" x2="520" y2="215" stroke="#666" stroke-width="2"/>
  <line x1="450" y1="175" x2="580" y2="215" stroke="#666" stroke-width="2"/>

  <!-- Level 2 nodes -->
  <circle cx="180" cy="240" r="25" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
  <text x="180" y="248" fill="#fff" text-anchor="middle" font-size="16" font-weight="bold">8</text>

  <circle cx="320" cy="240" r="25" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
  <text x="320" y="248" fill="#fff" text-anchor="middle" font-size="16" font-weight="bold">4</text>

  <circle cx="520" cy="240" r="25" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
  <text x="520" y="248" fill="#fff" text-anchor="middle" font-size="16" font-weight="bold">6</text>

  <circle cx="580" cy="240" r="25" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
  <text x="580" y="248" fill="#fff" text-anchor="middle" font-size="16" font-weight="bold">3</text>

  <!-- Properties -->
  <text x="20" y="320" fill="#e0e0e0" font-size="13">Max-Heap Property:</text>
  <text x="20" y="340" fill="#aaa" font-size="12">• Parent ≥ Children</text>
  <text x="20" y="355" fill="#aaa" font-size="12">• Root is the largest</text>
  <text x="20" y="370" fill="#aaa" font-size="12">• Parent of node i at (i-1)/2</text>
  <text x="20" y="385" fill="#aaa" font-size="12">• Left child at 2i+1</text>
  <text x="20" y="400" fill="#aaa" font-size="12">• Right child at 2i+2</text>

  <!-- Array representation -->
  <text x="350" y="320" fill="#e0e0e0" font-size="13">Array Representation:</text>
  <rect x="300" y="335" width="35" height="30" fill="#51cf66" stroke="#51cf66" stroke-width="1"/>
  <text x="317" y="356" fill="#000" text-anchor="middle" font-size="12">10</text>
  <rect x="340" y="335" width="35" height="30" fill="#4169e1" stroke="#4169e1" stroke-width="1"/>
  <text x="357" y="356" fill="#fff" text-anchor="middle" font-size="12">9</text>
  <rect x="380" y="335" width="35" height="30" fill="#4169e1" stroke="#4169e1" stroke-width="1"/>
  <text x="397" y="356" fill="#fff" text-anchor="middle" font-size="12">7</text>
  <rect x="420" y="335" width="35" height="30" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="1"/>
  <text x="437" y="356" fill="#fff" text-anchor="middle" font-size="12">8</text>
  <rect x="460" y="335" width="35" height="30" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="1"/>
  <text x="477" y="356" fill="#fff" text-anchor="middle" font-size="12">4</text>
  <rect x="500" y="335" width="35" height="30" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="1"/>
  <text x="517" y="356" fill="#fff" text-anchor="middle" font-size="12">6</text>

  <!-- Heapify example -->
  <text x="20" y="450" fill="#e0e0e0" font-size="13">Heapify: Move element down until heap property restored</text>
  <text x="20" y="468" fill="#aaa" font-size="11">If element &lt; child, swap with larger child and repeat</text>
</svg>

Advantages of Heap Sort

O(n log n) guaranteed: No worst-case O(n²) like quicksort
In-place sorting: Uses O(1) extra space
Good cache performance: Accesses array elements sequentially
Suitable for external sorting: Works well with disk I/O

When to Use Heap Sort

When you need guaranteed O(n log n) performance
When space is limited (need in-place sorting)
When you need a priority queue (heap is perfect for this)
When stability isn’t required

Quiz Time

Test your understanding of heap sort with these questions: