堆排序的两种建堆方式

前言

堆排序基于堆这种数据结构实现，而建堆是堆排序的关键前置步骤。不同的建堆方式会对堆排序的性能产生影响。本文我将深入讲解两种建堆方式 —— 自顶向下建堆和自底向上建堆，详细分析它们的原理、实现过程、时间复杂度、空间复杂度以及适用场景，并结合代码示例和图示，帮助读者全面掌握堆排序及其建堆方式。

一、堆排序基本概念

1.1 堆排序概述

堆排序是一种基于比较的排序算法，它利用堆这种数据结构来实现对数据的排序。堆排序的基本过程分为两个阶段：首先将待排序序列构建成一个堆，然后反复从堆顶取出最大（或最小）元素，并调整堆结构，直到堆为空，最终得到有序序列。

1.2 堆的定义与特性

堆是一种特殊的完全二叉树，满足以下特性：

• 大顶堆：每个节点的值都大于或等于其子节点的值，堆顶元素是整个堆中的最大值。

• 小顶堆：每个节点的值都小于或等于其子节点的值，堆顶元素是整个堆中的最小值。

在实际应用中，通常使用数组来存储堆，因为完全二叉树的特性使得数组可以高效地表示堆结构。对于数组中索引为 i 的元素，其左子节点索引为 2 * i + 1，右子节点索引为 2 * i + 2，父节点索引为 (i - 1) / 2（i > 0）。

二、自顶向下建堆

2.1 原理与过程

自顶向下建堆，也称为插入建堆。它的基本思路是从一个空堆开始，依次将待排序序列中的元素插入堆中，并在插入过程中通过调整堆结构，使堆始终保持堆的特性。具体过程如下：

1. 初始时，堆为空。

2. 依次取出待排序序列中的元素，将其插入到堆的末尾（即数组的末尾）。

3. 对新插入的元素进行向上调整（也称为上浮操作），将其与父节点比较，如果不满足堆的特性（大顶堆中元素小于父节点，小顶堆中元素大于父节点），则交换该元素与父节点的位置，继续向上比较，直到满足堆的特性为止。

4. 重复步骤 2 和 3，直到所有元素都插入到堆中。
   

2.2 代码实现

def sift_up(arr, i):while i > 0 and arr[(i - 1) // 2] < arr[i]:arr[(i - 1) // 2], arr[i] = arr[i], arr[(i - 1) // 2]i = (i - 1) // 2return arrdef build_heap_top_down(arr):for i in range(1, len(arr)):sift_up(arr, i)return arrdef heap_sort_top_down(arr):arr = build_heap_top_down(arr)for i in range(len(arr) - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]arr = sift_down(arr, 0, i - 1)return arrdef sift_down(arr, i, size):largest = ileft = 2 * i + 1right = 2 * i + 2if left < size and arr[left] > arr[largest]:largest = leftif right < size and arr[right] > arr[largest]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]sift_down(arr, largest, size)return arr

2.3 时间复杂度

在自顶向下建堆过程中，插入第 i 个元素时，最多需要向上调整 $\log i$ 次。因此，建堆的时间复杂度为 ${\sum }_{i=1}^n\log i$，通过数学推导可知，该求和结果近似为 $O(n\log n)$。加上后续的排序过程（每次调整堆的时间复杂度为 $O(\log n)$，共进行 $n-1$ 次，时间复杂度也为 $O(n\log n)$），整体堆排序的时间复杂度为 $O(n\log n)$。

2.4 空间复杂度

自顶向下建堆过程中，只需要额外的常数级空间来存储临时变量，因此空间复杂度为 $O(1)$。

三、自底向上建堆

3.1 原理与过程

自底向上建堆，也称为 Floyd 建堆。它的基本思路是从完全二叉树的最后一个非叶子节点开始，自下而上、从右到左依次对每个非叶子节点进行向下调整（也称为下沉操作），使整个二叉树满足堆的特性。具体过程如下：

1. 找到完全二叉树中最后一个非叶子节点，其索引为 n / 2 - 1（n 为元素个数）。

2. 从该节点开始，依次对每个非叶子节点进行向下调整操作。向下调整时，将节点与其子节点比较，如果不满足堆的特性，则将该节点与较大（大顶堆）或较小（小顶堆）的子节点交换位置，继续向下比较，直到满足堆的特性为止。

3. 重复步骤 2，直到对根节点也进行了调整，此时整个序列构建成了一个堆。
   

3.2 代码实现

def build_heap_bottom_up(arr):for i in range(len(arr) // 2 - 1, -1, -1):sift_down(arr, i, len(arr))return arrdef heap_sort_bottom_up(arr):arr = build_heap_bottom_up(arr)for i in range(len(arr) - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]arr = sift_down(arr, 0, i - 1)return arrdef sift_down(arr, i, size):largest = ileft = 2 * i + 1right = 2 * i + 2if left < size and arr[left] > arr[largest]:largest = leftif right < size and arr[right] > arr[largest]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]sift_down(arr, largest, size)return arr

3.3 时间复杂度

在自底向上建堆过程中，对于高度为 h 的节点，向下调整的时间复杂度为 $O(h)$。完全二叉树中高度为 h 的节点数最多为 $\frac{n}{2^{h+1}}$。通过对所有非叶子节点的调整时间进行求和计算，可得建堆的时间复杂度为 $O(n)$。加上后续的排序过程（时间复杂度为 $O(n\log n)$），整体堆排序的时间复杂度仍为 $O(n\log n)$，但由于建堆时间更优，整体性能相对自顶向下建堆更好。

3.4 空间复杂度

自底向上建堆同样只需要额外的常数级空间来存储临时变量，空间复杂度为 $O(1)$。

四、方式对比

对比项	自顶向下建堆	自底向上建堆
建堆思路	从空堆开始，依次插入元素并上浮调整	从最后一个非叶子节点开始，自下而上下沉调整
建堆时间复杂度	$O(n\log n)$	$O(n)$
整体时间复杂度	$O(n\log n)$	$O(n\log n)$
空间复杂度	$O(1)$	$O(1)$
性能特点	建堆过程相对较慢，整体性能略逊	建堆过程高效，整体性能更优

五、总结

5.1 稳定性

堆排序是一种不稳定的排序算法。在堆的调整过程中，相同元素的相对顺序可能会发生改变。例如，在大顶堆中，两个相同的元素，位于下方的元素可能会因为调整操作而移动到上方元素的前面。

5.2 应用场景

• 大规模数据排序：由于堆排序的时间复杂度稳定为 $O(n\log n)$，且空间复杂度为 $O(1)$，在处理大规模数据排序时，不需要额外的大量空间，适用于内存有限的环境。

• 优先队列实现：堆是实现优先队列的常用数据结构，堆排序的思想可以用于高效地维护优先队列，快速获取队列中的最大（或最小）元素。

堆排序作为经典的排序算法，其两种建堆方式各有特点。自顶向下建堆思路直观，易于理解，但建堆效率相对较低；自底向上建堆通过巧妙的下沉调整策略，实现了更高效的建堆过程，提升了整体性能。深入理解这两种建堆方式的原理、实现和性能差异，有助于我们在实际应用中根据具体需求选择合适的建堆方式，优化堆排序算法的性能。

同时如果你想了解堆排序的堆调整/堆化(heapify)和堆排序过程等内容和代码，可以进我主页查看之前的排序算法堆排章节相关知识，此篇建堆讲解仅作为临时补充，这里不做赘述，谢谢观看!

点击进入: 排序算法之高效排序:快速排序,归并排序,堆排序详解

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～