Heapsort 算法详解 | Baeldung中文网

1. 概述

Heapsort 是一种优雅且稳健的排序算法。它在时间复杂度上达到了最优，仅需 $O(n\log n)$ 时间对 n 个元素进行排序，这在基于比较的排序算法中是最优表现。

本文将直观地解释 Heapsort 的核心步骤和实现原理，帮助你更好地理解和应用这一经典算法。

2. 堆（Heap）

堆是一种特殊的二叉树结构，具有以下两个特性：

它是一棵完全二叉树
每个节点的值都大于等于其子节点的值（称为最大堆）

示意图如下：

我们可以使用 max-heapify 方法在 O(n) 时间内将任意完全二叉树转换为最大堆。

一个包含 n 个节点的完全二叉树可以用一个长度为 n 的数组 A 来紧凑表示。节点 i 的两个子节点索引分别为 2*i+1 和 2*i+2。

例如，节点 A[1] 的子节点是 A[3] 和 A[4]。下面是一个堆的数组表示示例：

3. 堆排序原理

排序过程主要包括以下几个步骤：

将数组转换为最大堆
将堆顶元素（最大值）与最后一个元素交换，缩小堆的范围
重新调整堆结构以维持堆的性质
重复上述步骤直到堆为空

3.1. 使用子数组表示堆

为了在排序过程中维护堆结构，我们需要一个可以处理数组子范围的“下沉”函数，我们称之为 sift-down：

algorithm sift_down(heap, start, end):
    // INPUT:
    //   heap - 表示堆的数组，start - 起始索引，end - 堆的结束边界
    // OUTPUT:
    //   原地修改数组，使 heap[start..end-1] 满足堆性质

    index <- start
    while index < end:
        left_child <- 2 * index + 1
        right_child <- 2 * index + 2

        if left_child >= end:
            return

        larger_child <- left_child
        if right_child < end and heap[left_child] < heap[right_child]:
            larger_child <- right_child

        if heap[index] < heap[larger_child]:
            swap(heap[index], heap[larger_child])
            index <- larger_child
        else:
            return

这个函数允许我们忽略 end 之后的元素，从而在逻辑上将数组划分为“堆”和“已排序”两部分。

3.2. 构建堆结构（Heapify）

我们可以用 sift-down 实现 heapify 函数，用于将数组转换为最大堆：

algorithm heapify(arr):
    // INPUT:
    //   arr - 待堆化的数组
    // OUTPUT:
    //   原地修改数组，使其满足最大堆性质

    start <- len(arr) // 2
    while start >= 0:
        sift_down(arr, start, len(arr))
        start <- start - 1

3.3. 将最大值放到正确位置

最大堆的根节点始终是当前堆中的最大值。为了升序排列，我们需要将它交换到数组末尾：

swap(A[0], A[n-1])

此时，堆结构可能被破坏，因此需要调用 sift-down 来修复堆。

例如，交换后节点 0 的值可能小于其子节点，如下图所示：

3.4. 使用 sift-down 修复堆

修复堆的过程如下：

从根节点开始，比较当前节点与两个子节点
选择较大的子节点进行交换
重复该过程直到堆性质恢复或到达叶子节点

3.5. 示例演示 sift-down

以一个具体示例展示 sift-down 的执行过程：

初始状态：

交换最大值后：

随后执行 sift-down，逐步修复堆结构：

最终堆结构恢复：

3.6. 完整排序过程示意

绿色表示堆区域，紫色表示已排序区域。堆大小逐步缩小，已排序区域逐步扩大：

3.7. Heapsort 完整伪代码

algorithm heapsort(arr):
    heapify(arr)
    end <- len(arr) - 1
    while end > 0:
        swap(arr[0], arr[end])
        end <- end - 1
        sift_down(arr, 0, end)

4. Heapsort 的时间复杂度

构建堆的时间为
每次 sift-down 操作最多需要 $O(\log n)$ 时间
共进行 n 次 sift-down，总时间为 $O(n \log n)$

因此，Heapsort 的时间复杂度为 **O(n log n)**，这是基于比较排序算法的最优性能。

5. Heapsort 与 Selection Sort 的对比

特性	Heapsort	Selection Sort
时间复杂度	O(n log n)	O(n²)
每轮比较次数	O(log n)	O(n)
优势	利用堆结构快速找到最大值	简单直观
缺点	实现略复杂	性能较差

Heapsort 可以看作是对 Selection Sort 的优化，利用堆结构将每次找最大值的操作从 O(n) 提升到 O(log n)。

6. Python 实现

6.1. 使用 Python 内置堆实现

Python 的 heapq 模块提供了一个最小堆实现。我们可以基于它实现一个简单的 Heapsort：

import heapq

def heapsort_simple(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

# 示例
arr = [53, 42, 30, 17, 13, 24, 9, 2, 5, 11]
sorted_arr = heapsort_simple(arr)
print("Sorted array is:", sorted_arr)

6.2. 手动实现 Heapsort

def sift_down(heap, start, end):
    index = start
    while index < end:
        left = 2 * index + 1
        right = 2 * index + 2
        if left >= end:
            break

        larger = left
        if right < end and heap[left] < heap[right]:
            larger = right

        if heap[index] < heap[larger]:
            heap[index], heap[larger] = heap[larger], heap[index]
            index = larger
        else:
            break

def heapify(arr):
    start = len(arr) // 2
    while start >= 0:
        sift_down(arr, start, len(arr))
        start -= 1

def heapsort(arr):
    heapify(arr)
    end = len(arr) - 1
    while end > 0:
        arr[0], arr[end] = arr[end], arr[0]
        end -= 1
        sift_down(arr, 0, end)

6.3. 支持多种数据类型排序

我们可以扩展代码以支持不同类型的数据，并允许自定义比较函数：

from typing import List, Callable

def sift_down(heap: List, start: int, end: int, compare: Callable):
    index = start
    while index < end:
        left = 2 * index + 1
        right = 2 * index + 2
        if left >= end:
            break

        larger = left
        if right < end and compare(heap[left], heap[right]):
            larger = right

        if compare(heap[index], heap[larger]):
            heap[index], heap[larger] = heap[larger], heap[index]
            index = larger
        else:
            break

def heapify(arr: List, compare: Callable):
    start = len(arr) // 2
    while start >= 0:
        sift_down(arr, start, len(arr), compare)
        start -= 1

def heapsort(arr: List, compare: Callable = lambda x, y: x < y):
    heapify(arr, compare)
    end = len(arr) - 1
    while end > 0:
        arr[0], arr[end] = arr[end], arr[0]
        end -= 1
        sift_down(arr, 0, end, compare)

✅ 示例：按字符串长度排序

arr = ["banana", "apple", "pear", "grape"]
heapsort(arr, compare=lambda x, y: len(x) < len(y))
print("Sorted by length:", arr)

7. 总结

Heapsort 是一种基于最大堆的排序算法，核心思想是：

构建最大堆
不断取出堆顶最大值并交换到数组末尾
缩小堆范围并修复堆结构

其时间复杂度为 **O(n log n)**，是基于比较排序算法中最优的实现之一。

⚠️ 虽然 Heapsort 在理论性能上优秀，但在实际应用中通常不如 QuickSort 或 MergeSort 快，因为它常数因子较大，缓存局部性较差。

✅ 优点：

时间复杂度稳定
原地排序（空间复杂度 O(1)）
适用于大数据量排序

❌ 缺点：

实现复杂度较高
不稳定排序（相同元素顺序可能改变）
缓存命中率低

你可以根据实际需求选择是否使用 Heapsort，但在学习算法和面试中，它是一个非常重要的知识点。

Persistence

REST

Security