Skip to content

11.7   Heap sort

Tip

Before reading this section, please make sure 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 creation" and "element extraction" operations we have already learned.

  1. Input the array and establish a min-heap, where the smallest element is at the heap's top.
  2. Continuously perform the extraction operation, recording the extracted elements in sequence to obtain a sorted list from smallest to largest.

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

11.7.1   Algorithm flow

Suppose the array length is \(n\), the heap sort process is as follows.

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

Tip

In fact, the element extraction operation also includes steps 2. and 3., with the addition of a popping element step.

Heap sort process

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   Heap sort process

In the code implementation, we used the sift-down function sift_down() from the "Heap" chapter. It is important to note that since the heap's length decreases as the maximum element is extracted, we need to add a length parameter \(n\) to the sift_down() function to specify the current effective length of the heap. The code is shown below:

heap_sort.py
def sift_down(nums: list[int], n: int, i: int):
    """堆的长度为 n ，从节点 i 开始，从顶至底堆化"""
    while True:
        # 判断节点 i, l, r 中值最大的节点，记为 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
        # 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i:
            break
        # 交换两节点
        nums[i], nums[ma] = nums[ma], nums[i]
        # 循环向下堆化
        i = ma

def heap_sort(nums: list[int]):
    """堆排序"""
    # 建堆操作：堆化除叶节点以外的其他所有节点
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # 从堆中提取最大元素，循环 n-1 轮
    for i in range(len(nums) - 1, 0, -1):
        # 交换根节点与最右叶节点（交换首元素与尾元素）
        nums[0], nums[i] = nums[i], nums[0]
        # 以根节点为起点，从顶至底进行堆化
        sift_down(nums, i, 0)
heap_sort.cpp
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(vector<int> &nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点
        swap(nums[i], nums[ma]);
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(vector<int> &nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftDown(nums, nums.size(), i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.size() - 1; i > 0; --i) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        swap(nums[0], nums[i]);
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}
heap_sort.java
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i)
            break;
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(int[] nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}
heap_sort.cs
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void SiftDown(int[] nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i)
            break;
        // 交换两节点
        (nums[ma], nums[i]) = (nums[i], nums[ma]);
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void HeapSort(int[] nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.Length / 2 - 1; i >= 0; i--) {
        SiftDown(nums, nums.Length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.Length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        (nums[i], nums[0]) = (nums[0], nums[i]);
        // 以根节点为起点，从顶至底进行堆化
        SiftDown(nums, i, 0);
    }
}
heap_sort.go
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
func siftDown(nums *[]int, n, i int) {
    for true {
        // 判断节点 i, l, r 中值最大的节点，记为 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
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i {
            break
        }
        // 交换两节点
        (*nums)[i], (*nums)[ma] = (*nums)[ma], (*nums)[i]
        // 循环向下堆化
        i = ma
    }
}

/* 堆排序 */
func heapSort(nums *[]int) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for i := len(*nums)/2 - 1; i >= 0; i-- {
        siftDown(nums, len(*nums), i)
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for i := len(*nums) - 1; i > 0; i-- {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        (*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0)
    }
}
heap_sort.swift
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
func siftDown(nums: inout [Int], n: Int, i: Int) {
    var i = i
    while true {
        // 判断节点 i, l, r 中值最大的节点，记为 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
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i {
            break
        }
        // 交换两节点
        nums.swapAt(i, ma)
        // 循环向下堆化
        i = ma
    }
}

/* 堆排序 */
func heapSort(nums: inout [Int]) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for i in stride(from: nums.count / 2 - 1, through: 0, by: -1) {
        siftDown(nums: &nums, n: nums.count, i: i)
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for i in nums.indices.dropFirst().reversed() {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        nums.swapAt(0, i)
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums: &nums, n: i, i: 0)
    }
}
heap_sort.js
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
function siftDown(nums, n, i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma === i) {
            break;
        }
        // 交换两节点
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
function heapSort(nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (let i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}
heap_sort.ts
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
function siftDown(nums: number[], n: number, i: number): void {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma === i) {
            break;
        }
        // 交换两节点
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
function heapSort(nums: number[]): void {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (let i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}
heap_sort.dart
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(List<int> nums, int n, int i) {
  while (true) {
    // 判断节点 i, l, r 中值最大的节点，记为 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;
    // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
    if (ma == i) break;
    // 交换两节点
    int temp = nums[i];
    nums[i] = nums[ma];
    nums[ma] = temp;
    // 循环向下堆化
    i = ma;
  }
}

/* 堆排序 */
void heapSort(List<int> nums) {
  // 建堆操作：堆化除叶节点以外的其他所有节点
  for (int i = nums.length ~/ 2 - 1; i >= 0; i--) {
    siftDown(nums, nums.length, i);
  }
  // 从堆中提取最大元素，循环 n-1 轮
  for (int i = nums.length - 1; i > 0; i--) {
    // 交换根节点与最右叶节点（交换首元素与尾元素）
    int tmp = nums[0];
    nums[0] = nums[i];
    nums[i] = tmp;
    // 以根节点为起点，从顶至底进行堆化
    siftDown(nums, i, 0);
  }
}
heap_sort.rs
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
fn sift_down(nums: &mut [i32], n: usize, mut i: usize) {
    loop {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i {
            break;
        }
        // 交换两节点
        let temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
fn heap_sort(nums: &mut [i32]) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for i in (0..=nums.len() / 2 - 1).rev() {
        sift_down(nums, nums.len(), i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for i in (1..=nums.len() - 1).rev() {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        let tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        sift_down(nums, i, 0);
    }
}
heap_sort.c
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(int nums[], int n, int i) {
    while (1) {
        // 判断节点 i, l, r 中值最大的节点，记为 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;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(int nums[], int n) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(nums, n, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = n - 1; i > 0; --i) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}
heap_sort.kt
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
fun siftDown(nums: IntArray, n: Int, li: Int) {
    var i = li
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 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
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) 
            break
        // 交换两节点
        val temp = nums[i]
        nums[i] = nums[ma]
        nums[ma] = temp
        // 循环向下堆化
        i = ma
    }
}

/* 堆排序 */
fun heapSort(nums: IntArray) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (i in nums.size / 2 - 1 downTo 0) {
        siftDown(nums, nums.size, i)
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (i in nums.size - 1 downTo 1) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        val temp = nums[0]
        nums[0] = nums[i]
        nums[i] = temp
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0)
    }
}
heap_sort.rb
### 堆的长度为 n ，从节点 i 开始，从顶至底堆化 ###
def sift_down(nums, n, i)
  while true
    # 判断节点 i, l, r 中值最大的节点，记为 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]
    # 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
    break if ma == i
    # 交换两节点
    nums[i], nums[ma] = nums[ma], nums[i]
    # 循环向下堆化
    i = ma
  end
end

### 堆排序 ###
def heap_sort(nums)
  # 建堆操作：堆化除叶节点以外的其他所有节点
  (nums.length / 2 - 1).downto(0) do |i|
    sift_down(nums, nums.length, i)
  end
  # 从堆中提取最大元素，循环 n-1 轮
  (nums.length - 1).downto(1) do |i|
    # 交换根节点与最右叶节点（交换首元素与尾元素）
    nums[0], nums[i] = nums[i], nums[0]
    # 以根节点为起点，从顶至底进行堆化
    sift_down(nums, i, 0)
  end
end
heap_sort.zig
[class]{}-[func]{siftDown}

[class]{}-[func]{heapSort}
Code Visualization

11.7.2   Algorithm characteristics

  • Time complexity is \(O(n \log n)\), non-adaptive sort: The heap creation uses \(O(n)\) time. Extracting the largest element from the heap takes \(O(\log n)\) time, looping for \(n - 1\) rounds.
  • Space complexity is \(O(1)\), in-place sort: A few pointer variables use \(O(1)\) space. The element swapping and heapifying operations are performed on the original array.
  • Non-stable sort: The relative positions of equal elements may change during the swapping of the heap's top and bottom elements.
Feel free to drop your insights, questions or suggestions