目录
1. 什么是堆排序
堆排序（Heap Sort）是一种基于比较的排序算法，它利用了堆这一数据结构的特性。堆是一种完全二叉树，并且满足堆的性质：
- 最大堆：每个节点的值都不小于其子节点的值。
- 最小堆：每个节点的值都不大于其子节点的值。
堆排序将待排序的数组构建成堆结构，并通过反复调整堆，最终得到一个排序好的数组。堆排序是一个不稳定的排序算法，它的时间复杂度为 O(nlogn)O(n \log n)。
2. 堆排序的原理
堆排序的基本思路如下：
- 构建最大堆：将待排序数组构建成一个最大堆，使得堆顶元素（最大元素）为整个数组的最大值。
- 交换堆顶元素与最后一个元素：将堆顶元素与堆的最后一个元素交换位置。
- 调整堆：每次交换后，堆的结构会被破坏，因此需要对堆顶元素进行下沉操作，使其重新符合堆的性质。
- 重复步骤 2 和 3：继续进行交换和调整，直到堆的大小为 1。
3. 堆排序的步骤
堆排序的具体步骤如下：
- 构建最大堆：从最后一个非叶子节点开始，依次对每个节点执行下沉操作，将数组调整成最大堆。
- 交换堆顶元素和最后一个元素：每次将最大元素移到数组的末尾。
- 重新调整堆：在交换后的数组中，堆的根节点被破坏，需要通过下沉操作恢复堆的性质。
- 继续交换和调整：重复步骤 2 和 3，直到堆只剩一个元素。
4. 堆排序的实现
PHP 代码实现
function heapify(&$arr, $n, $i) {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $n && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if ($largest != $i) {
// 交换
list($arr[$i], $arr[$largest]) = [$arr[$largest], $arr[$i]];
heapify($arr, $n, $largest);
}
}
function heapSort(&$arr) {
$n = count($arr);
// 构建最大堆
for ($i = floor($n / 2) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
// 排序过程
for ($i = $n - 1; $i > 0; $i--) {
// 将堆顶元素（最大元素）与当前元素交换
list($arr[0], $arr[$i]) = [$arr[$i], $arr[0]];
// 调整堆
heapify($arr, $i, 0);
}
}
// 测试代码
$arr = [12, 11, 13, 5, 6, 7];
heapSort($arr);
print_r($arr);
输出结果
Array
(
[0] => 5
[1] => 6
[2] => 7
[3] => 11
[4] => 12
[5] => 13
)
Python 代码实现
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # 交换
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 排序过程
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 交换堆顶元素
heapify(arr, i, 0)
# 测试代码
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)
输出结果
[5, 6, 7, 11, 12, 13]
5. 堆排序的时间复杂度
- 时间复杂度：
- 构建最大堆：需要对每个非叶子节点执行一次下沉操作，时间复杂度为 O(n)O(n)。
- 排序过程：每次交换堆顶元素后，需要重新调整堆，调整堆的时间复杂度为 O(logn)O(\log n)，需要执行 n−1n-1 次交换操作。因此，排序过程的时间复杂度为 O(nlogn)O(n \log n)。
- 空间复杂度：堆排序是一种原地排序算法，它只需要常数级别的额外空间，因此空间复杂度为 O(1)。
6. 应用场景
- 优先队列：堆排序的最大堆和最小堆性质常用于实现优先队列。
- 实时数据流：堆排序在动态数据中可以保持有序性，特别适用于流数据的实时排序。
- 排序算法选择：堆排序不依赖于数据的初始顺序，适用于大数据的排序，尤其当内存受限时，堆排序由于其 O(nlogn)O(n \log n) 的时间复杂度表现优异。
7. 参考资料
- 《算法导论》第 6 章 – 堆排序
- LeetCode 题解：https://leetcode.cn/problems/kth-largest-element-in-an-array/
- GeeksForGeeks 堆排序：https://www.geeksforgeeks.org/heap-sort/
发表回复