Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 11.7 Heap Sort

Tip

Before reading this section, please ensure you have completed the "Heap" chapter.

Heap sort is an efficient sorting algorithm based on the heap data structure. We can implement heap sort using the heap construction and element removal operations introduced earlier.

1. Input the array and build a min-heap, at which point the smallest element is at the heap top.
2. Continuously perform element removal operations and record the removed elements in order to obtain a sequence sorted in ascending order.

Although the above method is feasible, it requires an additional array to save the popped elements, which is quite wasteful of space. In practice, we usually use a more elegant implementation method.

## 11.7.1 Algorithm Flow

Assume the array length is \(n\). The flow of heap sort is shown in Figure 11-12.

1. Input the array and build a max-heap. After completion, the largest element is at the heap top.
2. Swap the heap top element (first element) with the heap bottom element (last element). After the swap is complete, reduce the heap length by \(1\) and increase the count of sorted elements by \(1\).
3. Starting from the heap top element, perform a top-to-bottom heapify operation (sift down). After heapify is complete, the heap property is restored.
4. Repeat steps `2.` and `3.` After \(n - 1\) rounds, the array is sorted.

Tip

In fact, the element removal operation also includes steps `2.` and `3.`, with the additional step of removing the element.

<1><2><3><4><5><6><7><8><9><10><11><12>

Figure 11-12 Heap sort steps

In the code below, we use the same `sift_down()` function for top-to-bottom heapify as in the "Heap" chapter. It is worth noting that since the heap length decreases as the largest element is extracted, we need to add a length parameter \(n\) to `sift_down()` to specify the current effective length of the heap. The code is as follows:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
heap_sort.py

    def sift_down(nums: list[int], n: int, i: int):
        """Heap length is n, start heapifying node i, from top to bottom"""
        while True:
            # Determine the largest node among i, l, r, noted as 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
            # If node i is the largest or indices l, r are out of bounds, no further heapification needed, break
            if ma == i:
                break
            # Swap two nodes
            nums[i], nums[ma] = nums[ma], nums[i]
            # Loop downwards heapification
            i = ma

    def heap_sort(nums: list[int]):
        """Heap sort"""
        # Build heap operation: heapify all nodes except leaves
        for i in range(len(nums) // 2 - 1, -1, -1):
            sift_down(nums, len(nums), i)
        # Extract the largest element from the heap and repeat for n-1 rounds
        for i in range(len(nums) - 1, 0, -1):
            # Swap the root node with the rightmost leaf node (swap the first element with the last element)
            nums[0], nums[i] = nums[i], nums[0]
            # Start heapifying the root node, from top to bottom
            sift_down(nums, i, 0)

heap_sort.cpp

    /* Heap length is n, start heapifying node i, from top to bottom */
    void siftDown(vector<int> &nums, int n, int i) {
        while (true) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            // Swap two nodes
            if (ma == i) {
                break;
            }
            // Swap two nodes
            swap(nums[i], nums[ma]);
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    void heapSort(vector<int> &nums) {
        // Build heap operation: heapify all nodes except leaves
        for (int i = nums.size() / 2 - 1; i >= 0; --i) {
            siftDown(nums, nums.size(), i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (int i = nums.size() - 1; i > 0; --i) {
            // Delete node
            swap(nums[0], nums[i]);
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0);
        }
    }

heap_sort.java

    /* Heap length is n, start heapifying node i, from top to bottom */
    void siftDown(int[] nums, int n, int i) {
        while (true) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            // Swap two nodes
            if (ma == i)
                break;
            // Swap two nodes
            int temp = nums[i];
            nums[i] = nums[ma];
            nums[ma] = temp;
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    void heapSort(int[] nums) {
        // Build heap operation: heapify all nodes except leaves
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (int i = nums.length - 1; i > 0; i--) {
            // Delete node
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0);
        }
    }

heap_sort.cs

    /* Heap length is n, start heapifying node i, from top to bottom */
    void SiftDown(int[] nums, int n, int i) {
        while (true) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            // Swap two nodes
            if (ma == i)
                break;
            // Swap two nodes
            (nums[ma], nums[i]) = (nums[i], nums[ma]);
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    void HeapSort(int[] nums) {
        // Build heap operation: heapify all nodes except leaves
        for (int i = nums.Length / 2 - 1; i >= 0; i--) {
            SiftDown(nums, nums.Length, i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (int i = nums.Length - 1; i > 0; i--) {
            // Delete node
            (nums[i], nums[0]) = (nums[0], nums[i]);
            // Start heapifying the root node, from top to bottom
            SiftDown(nums, i, 0);
        }
    }

heap_sort.go

    /* Heap length is n, start heapifying node i, from top to bottom */
    func siftDown(nums *[]int, n, i int) {
        for true {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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
            }
            // Swap two nodes
            if ma == i {
                break
            }
            // Swap two nodes
            (*nums)[i], (*nums)[ma] = (*nums)[ma], (*nums)[i]
            // Loop downwards heapification
            i = ma
        }
    }

    /* Heap sort */
    func heapSort(nums *[]int) {
        // Build heap operation: heapify all nodes except leaves
        for i := len(*nums)/2 - 1; i >= 0; i-- {
            siftDown(nums, len(*nums), i)
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for i := len(*nums) - 1; i > 0; i-- {
            // Delete node
            (*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0)
        }
    }

heap_sort.swift

    /* Heap length is n, start heapifying node i, from top to bottom */
    func siftDown(nums: inout [Int], n: Int, i: Int) {
        var i = i
        while true {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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
            }
            // Swap two nodes
            if ma == i {
                break
            }
            // Swap two nodes
            nums.swapAt(i, ma)
            // Loop downwards heapification
            i = ma
        }
    }

    /* Heap sort */
    func heapSort(nums: inout [Int]) {
        // Build heap operation: heapify all nodes except leaves
        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 and repeat for n-1 rounds
        for i in nums.indices.dropFirst().reversed() {
            // Delete node
            nums.swapAt(0, i)
            // Start heapifying the root node, from top to bottom
            siftDown(nums: &nums, n: i, i: 0)
        }
    }

heap_sort.js

    /* Heap length is n, start heapifying node i, from top to bottom */
    function siftDown(nums, n, i) {
        while (true) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            }
            // Swap two nodes
            if (ma === i) {
                break;
            }
            // Swap two nodes
            [nums[i], nums[ma]] = [nums[ma], nums[i]];
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    function heapSort(nums) {
        // Build heap operation: heapify all nodes except leaves
        for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (let i = nums.length - 1; i > 0; i--) {
            // Delete node
            [nums[0], nums[i]] = [nums[i], nums[0]];
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0);
        }
    }

heap_sort.ts

    /* Heap length is n, start heapifying node i, from top to bottom */
    function siftDown(nums: number[], n: number, i: number): void {
        while (true) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            }
            // Swap two nodes
            if (ma === i) {
                break;
            }
            // Swap two nodes
            [nums[i], nums[ma]] = [nums[ma], nums[i]];
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    function heapSort(nums: number[]): void {
        // Build heap operation: heapify all nodes except leaves
        for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (let i = nums.length - 1; i > 0; i--) {
            // Delete node
            [nums[0], nums[i]] = [nums[i], nums[0]];
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0);
        }
    }

heap_sort.dart

    /* Heap length is n, start heapifying node i, from top to bottom */
    void siftDown(List<int> nums, int n, int i) {
      while (true) {
        // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
        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;
        // Swap two nodes
        if (ma == i) break;
        // Swap two nodes
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // Loop downwards heapification
        i = ma;
      }
    }

    /* Heap sort */
    void heapSort(List<int> nums) {
      // Build heap operation: heapify all nodes except leaves
      for (int i = nums.length ~/ 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
      }
      // Extract the largest element from the heap and repeat for n-1 rounds
      for (int i = nums.length - 1; i > 0; i--) {
        // Delete node
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // Start heapifying the root node, from top to bottom
        siftDown(nums, i, 0);
      }
    }

heap_sort.rs

    /* Heap length is n, start heapifying node i, from top to bottom */
    fn sift_down(nums: &mut [i32], n: usize, mut i: usize) {
        loop {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            }
            // Swap two nodes
            if ma == i {
                break;
            }
            // Swap two nodes
            nums.swap(i, ma);
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    fn heap_sort(nums: &mut [i32]) {
        // Build heap operation: heapify all nodes except leaves
        for i in (0..nums.len() / 2).rev() {
            sift_down(nums, nums.len(), i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for i in (1..nums.len()).rev() {
            // Delete node
            nums.swap(0, i);
            // Start heapifying the root node, from top to bottom
            sift_down(nums, i, 0);
        }
    }

heap_sort.c

    /* Heap length is n, start heapifying node i, from top to bottom */
    void siftDown(int nums[], int n, int i) {
        while (1) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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;
            // Swap two nodes
            if (ma == i) {
                break;
            }
            // Swap two nodes
            int temp = nums[i];
            nums[i] = nums[ma];
            nums[ma] = temp;
            // Loop downwards heapification
            i = ma;
        }
    }

    /* Heap sort */
    void heapSort(int nums[], int n) {
        // Build heap operation: heapify all nodes except leaves
        for (int i = n / 2 - 1; i >= 0; --i) {
            siftDown(nums, n, i);
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (int i = n - 1; i > 0; --i) {
            // Delete node
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0);
        }
    }

heap_sort.kt

    /* Heap length is n, start heapifying node i, from top to bottom */
    fun siftDown(nums: IntArray, n: Int, li: Int) {
        var i = li
        while (true) {
            // If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
            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
            // Swap two nodes
            if (ma == i)
                break
            // Swap two nodes
            val temp = nums[i]
            nums[i] = nums[ma]
            nums[ma] = temp
            // Loop downwards heapification
            i = ma
        }
    }

    /* Heap sort */
    fun heapSort(nums: IntArray) {
        // Build heap operation: heapify all nodes except leaves
        for (i in nums.size / 2 - 1 downTo 0) {
            siftDown(nums, nums.size, i)
        }
        // Extract the largest element from the heap and repeat for n-1 rounds
        for (i in nums.size - 1 downTo 1) {
            // Delete node
            val temp = nums[0]
            nums[0] = nums[i]
            nums[i] = temp
            // Start heapifying the root node, from top to bottom
            siftDown(nums, i, 0)
        }
    }

heap_sort.rb

    ### Heap length is n, heapify from node i, top to bottom ###
    def sift_down(nums, n, i)
      while true
        # If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
        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]
        # Swap two nodes
        break if ma == i
        # Swap two nodes
        nums[i], nums[ma] = nums[ma], nums[i]
        # Loop downwards heapification
        i = ma
      end
    end

    ### Heap sort ###
    def heap_sort(nums)
      # Build heap operation: heapify all nodes except leaves
      (nums.length / 2 - 1).downto(0) do |i|
        sift_down(nums, nums.length, i)
      end
      # Extract the largest element from the heap and repeat for n-1 rounds
      (nums.length - 1).downto(1) do |i|
        # Delete node
        nums[0], nums[i] = nums[i], nums[0]
        # Start heapifying the root node, from top to bottom
        sift_down(nums, i, 0)
      end
    end

## 11.7.2 Algorithm Characteristics

- Time complexity is \(O(n \log n)\); heap sort is non-adaptive: Heap construction takes \(O(n)\) time. Extracting the largest element from the heap takes \(O(\log n)\) time, and this is repeated for a total of \(n - 1\) rounds.
- Space complexity is \(O(1)\); heap sort is in-place: A few pointer variables use \(O(1)\) space. Element swapping and heapify are both performed on the original array.
- Unstable sorting: When swapping the heap top element and heap bottom element, the relative positions of equal elements may change.

##### Feel free to drop your insights, questions or suggestions