Skip to content

11.7   Heap sort

Tip

Before reading this section, make sure you have completed the chapter on heaps.

Heap sort is an efficient sorting algorithm built on the heap data structure. We can implement it with the heap-building and removal operations we have already learned.

  1. Build a min heap from the input array. The smallest element is now at the root.
  2. Repeatedly remove the root and record the removed elements to obtain an ascending sequence.

Although this works, it requires an extra array to store the removed elements, wasting space. In practice, we usually use a more elegant implementation.

11.7.1   Algorithm steps

For an array of length \(n\), heap sort proceeds as shown below.

  1. Build a max heap from the input array. The largest element is now at the root.
  2. Swap the root, the first element, with the last element of the heap. Reduce the heap's length by \(1\) and increase the number of sorted elements by \(1\).
  3. Starting at the root, sift down to restore the heap property.
  4. Repeat steps 2. and 3.. After \(n - 1\) rounds, the array is sorted.

Tip

In fact, removing the root of a heap also includes steps 2. and 3., with the additional step of removing an element from the array.

Steps of heap sort

heap_sort_step2

heap_sort_step3

heap_sort_step4

heap_sort_step5

heap_sort_step6

heap_sort_step7

heap_sort_step8

heap_sort_step9

heap_sort_step10

heap_sort_step11

heap_sort_step12

Figure 11-12   Steps of heap sort

The implementation uses the same sift_down() function introduced in the heap chapter. Because the heap shrinks as maximum elements are extracted, add a length parameter \(n\) to specify its current valid length. The code is as follows:

heap_sort.py
def sift_down(nums: list[int], n: int, i: int):
    """Sift down from node i in a heap of size n"""
    while True:
        # Find the node with the largest value among i, l, and r, and store its index in ma
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        if l < n and nums[l] > nums[ma]:
            ma = l
        if r < n and nums[r] > nums[ma]:
            ma = r
        # Stop if node i is largest or both child indices l and r are out of bounds
        if ma == i:
            break
        # Swap the two nodes
        nums[i], nums[ma] = nums[ma], nums[i]
        # Continue sifting down
        i = ma

def heap_sort(nums: list[int]):
    """Heap sort"""
    # Build the heap by sifting down from every non-leaf node
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # Extract the largest element from the heap, repeating for n-1 rounds
    for i in range(len(nums) - 1, 0, -1):
        # Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        nums[0], nums[i] = nums[i], nums[0]
        # Sift down starting at the root
        sift_down(nums, i, 0)
heap_sort.cpp
/* Sift down from node i in a heap of size n */
void siftDown(vector<int> &nums, int n, int i) {
    while (true) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma == i) {
            break;
        }
        // Swap the two nodes
        swap(nums[i], nums[ma]);
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
void heapSort(vector<int> &nums) {
    // Build the heap by sifting down from every non-leaf node
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftDown(nums, nums.size(), i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (int i = nums.size() - 1; i > 0; --i) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        swap(nums[0], nums[i]);
        // Sift down starting at the root
        siftDown(nums, i, 0);
    }
}
heap_sort.java
/* Sift down from node i in a heap of size n */
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma == i)
            break;
        // Swap the two nodes
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
void heapSort(int[] nums) {
    // Build the heap by sifting down from every non-leaf node
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (int i = nums.length - 1; i > 0; i--) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // Sift down starting at the root
        siftDown(nums, i, 0);
    }
}
heap_sort.cs
/* Sift down from node i in a heap of size n */
void SiftDown(int[] nums, int n, int i) {
    while (true) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma == i)
            break;
        // Swap the two nodes
        (nums[ma], nums[i]) = (nums[i], nums[ma]);
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
void HeapSort(int[] nums) {
    // Build the heap by sifting down from every non-leaf node
    for (int i = nums.Length / 2 - 1; i >= 0; i--) {
        SiftDown(nums, nums.Length, i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (int i = nums.Length - 1; i > 0; i--) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        (nums[i], nums[0]) = (nums[0], nums[i]);
        // Sift down starting at the root
        SiftDown(nums, i, 0);
    }
}
heap_sort.go
/* Sift down from node i in a heap of size n */
func siftDown(nums *[]int, n, i int) {
    for true {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        l := 2*i + 1
        r := 2*i + 2
        ma := i
        if l < n && (*nums)[l] > (*nums)[ma] {
            ma = l
        }
        if r < n && (*nums)[r] > (*nums)[ma] {
            ma = r
        }
        // Stop if node i is largest or both child indices l and r are out of bounds
        if ma == i {
            break
        }
        // Swap the two nodes
        (*nums)[i], (*nums)[ma] = (*nums)[ma], (*nums)[i]
        // Continue sifting down
        i = ma
    }
}

/* Heap sort */
func heapSort(nums *[]int) {
    // Build the heap by sifting down from every non-leaf node
    for i := len(*nums)/2 - 1; i >= 0; i-- {
        siftDown(nums, len(*nums), i)
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for i := len(*nums) - 1; i > 0; i-- {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        (*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
        // Sift down starting at the root
        siftDown(nums, i, 0)
    }
}
heap_sort.swift
/* Sift down from node i in a heap of size n */
func siftDown(nums: inout [Int], n: Int, i: Int) {
    var i = i
    while true {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        let l = 2 * i + 1
        let r = 2 * i + 2
        var ma = i
        if l < n, nums[l] > nums[ma] {
            ma = l
        }
        if r < n, nums[r] > nums[ma] {
            ma = r
        }
        // Stop if node i is largest or both child indices l and r are out of bounds
        if ma == i {
            break
        }
        // Swap the two nodes
        nums.swapAt(i, ma)
        // Continue sifting down
        i = ma
    }
}

/* Heap sort */
func heapSort(nums: inout [Int]) {
    // Build the heap by sifting down from every non-leaf node
    for i in stride(from: nums.count / 2 - 1, through: 0, by: -1) {
        siftDown(nums: &nums, n: nums.count, i: i)
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for i in nums.indices.dropFirst().reversed() {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        nums.swapAt(0, i)
        // Sift down starting at the root
        siftDown(nums: &nums, n: i, i: 0)
    }
}
heap_sort.js
/* Sift down from node i in a heap of size n */
function siftDown(nums, n, i) {
    while (true) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let ma = i;
        if (l < n && nums[l] > nums[ma]) {
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]) {
            ma = r;
        }
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma === i) {
            break;
        }
        // Swap the two nodes
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
function heapSort(nums) {
    // Build the heap by sifting down from every non-leaf node
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (let i = nums.length - 1; i > 0; i--) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // Sift down starting at the root
        siftDown(nums, i, 0);
    }
}
heap_sort.ts
/* Sift down from node i in a heap of size n */
function siftDown(nums: number[], n: number, i: number): void {
    while (true) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let ma = i;
        if (l < n && nums[l] > nums[ma]) {
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]) {
            ma = r;
        }
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma === i) {
            break;
        }
        // Swap the two nodes
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
function heapSort(nums: number[]): void {
    // Build the heap by sifting down from every non-leaf node
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (let i = nums.length - 1; i > 0; i--) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // Sift down starting at the root
        siftDown(nums, i, 0);
    }
}
heap_sort.dart
/* Sift down from node i in a heap of size n */
void siftDown(List<int> nums, int n, int i) {
  while (true) {
    // Find the node with the largest value among i, l, and r, and store its index in ma
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int ma = i;
    if (l < n && nums[l] > nums[ma]) ma = l;
    if (r < n && nums[r] > nums[ma]) ma = r;
    // Stop if node i is largest or both child indices l and r are out of bounds
    if (ma == i) break;
    // Swap the two nodes
    int temp = nums[i];
    nums[i] = nums[ma];
    nums[ma] = temp;
    // Continue sifting down
    i = ma;
  }
}

/* Heap sort */
void heapSort(List<int> nums) {
  // Build the heap by sifting down from every non-leaf node
  for (int i = nums.length ~/ 2 - 1; i >= 0; i--) {
    siftDown(nums, nums.length, i);
  }
  // Extract the largest element from the heap, repeating for n-1 rounds
  for (int i = nums.length - 1; i > 0; i--) {
    // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
    int tmp = nums[0];
    nums[0] = nums[i];
    nums[i] = tmp;
    // Sift down starting at the root
    siftDown(nums, i, 0);
  }
}
heap_sort.rs
/* Sift down from node i in a heap of size n */
fn sift_down(nums: &mut [i32], n: usize, mut i: usize) {
    loop {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let mut ma = i;
        if l < n && nums[l] > nums[ma] {
            ma = l;
        }
        if r < n && nums[r] > nums[ma] {
            ma = r;
        }
        // Stop if node i is largest or both child indices l and r are out of bounds
        if ma == i {
            break;
        }
        // Swap the two nodes
        nums.swap(i, ma);
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
fn heap_sort(nums: &mut [i32]) {
    // Build the heap by sifting down from every non-leaf node
    for i in (0..nums.len() / 2).rev() {
        sift_down(nums, nums.len(), i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for i in (1..nums.len()).rev() {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        nums.swap(0, i);
        // Sift down starting at the root
        sift_down(nums, i, 0);
    }
}
heap_sort.c
/* Sift down from node i in a heap of size n */
void siftDown(int nums[], int n, int i) {
    while (1) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma == i) {
            break;
        }
        // Swap the two nodes
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // Continue sifting down
        i = ma;
    }
}

/* Heap sort */
void heapSort(int nums[], int n) {
    // Build the heap by sifting down from every non-leaf node
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(nums, n, i);
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (int i = n - 1; i > 0; --i) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // Sift down starting at the root
        siftDown(nums, i, 0);
    }
}
heap_sort.kt
/* Sift down from node i in a heap of size n */
fun siftDown(nums: IntArray, n: Int, li: Int) {
    var i = li
    while (true) {
        // Find the node with the largest value among i, l, and r, and store its index in ma
        val l = 2 * i + 1
        val r = 2 * i + 2
        var ma = i
        if (l < n && nums[l] > nums[ma]) 
            ma = l
        if (r < n && nums[r] > nums[ma]) 
            ma = r
        // Stop if node i is largest or both child indices l and r are out of bounds
        if (ma == i) 
            break
        // Swap the two nodes
        val temp = nums[i]
        nums[i] = nums[ma]
        nums[ma] = temp
        // Continue sifting down
        i = ma
    }
}

/* Heap sort */
fun heapSort(nums: IntArray) {
    // Build the heap by sifting down from every non-leaf node
    for (i in nums.size / 2 - 1 downTo 0) {
        siftDown(nums, nums.size, i)
    }
    // Extract the largest element from the heap, repeating for n-1 rounds
    for (i in nums.size - 1 downTo 1) {
        // Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
        val temp = nums[0]
        nums[0] = nums[i]
        nums[i] = temp
        // Sift down starting at the root
        siftDown(nums, i, 0)
    }
}
heap_sort.rb
### Sift down from node i in a heap of size n ###
def sift_down(nums, n, i)
  while true
    # Find the node with the largest value among i, l, and r, and store its index in ma
    l = 2 * i + 1
    r = 2 * i + 2
    ma = i
    ma = l if l < n && nums[l] > nums[ma]
    ma = r if r < n && nums[r] > nums[ma]
    # Stop if node i is largest or both child indices l and r are out of bounds
    break if ma == i
    # Swap the two nodes
    nums[i], nums[ma] = nums[ma], nums[i]
    # Continue sifting down
    i = ma
  end
end

### Heap sort ###
def heap_sort(nums)
  # Build the heap by sifting down from every non-leaf node
  (nums.length / 2 - 1).downto(0) do |i|
    sift_down(nums, nums.length, i)
  end
  # Extract the largest element from the heap, repeating for n-1 rounds
  (nums.length - 1).downto(1) do |i|
    # Swap the root with the rightmost leaf on the last level (the first and last elements of the current heap)
    nums[0], nums[i] = nums[i], nums[0]
    # Sift down starting at the root
    sift_down(nums, i, 0)
  end
end
Visualize execution

11.7.2   Algorithm properties

  • Time complexity: \(O(n \log n)\); not adaptive. Building the heap takes \(O(n)\) time. Extracting its maximum takes \(O(\log n)\) time and is repeated \(n - 1\) times.
  • Space complexity: \(O(1)\); in-place. A few pointer variables use \(O(1)\) space. Swapping and sifting take place within the original array.
  • Not stable. Swapping the root with the last element of the heap may change the relative order of equal elements.
Share your insights, questions, or suggestions in the comments