堆和堆排序

发表于 2025/11/03 更新于 2025/11/04

作者 CrabPeelMyShell

11 分钟阅读

堆由“优先队列”引出；

优先队列的定义与操作

定义：与标准队列的“先进先出” 不同，优先队列允许弹出具有最高优先级的对象，一般定义 0 为最高优先级。
优先队列的两种简单实现

多队列 (Multiple Queues)
- 方法：创建一个包含 M 个队列的数组，每个队列对应一个优先级。
- 分析：Push 操作为 $\Theta(1)$ ，但 Top 和 Pop 为 $O(M)$ 。但是这个方法限制了优先级范围（只能为整数），并且每需要一个优先级就要多一个队列，空间开销大。
AVL 树 (AVL Trees)
- 方法：使用 AVL 树存储对象，按优先级排序。
- 分析：插入、访问顶部和移除操作均为 $\Theta(ln(n))$ ，但想要维持树的平衡有显著开销；

Binary Min-Heap 定义： 非空二叉树，且子节点<=父节点；如果有子树，那么也都是二叉最小堆。

==两个子树之间没有任何必然关系==

Top ：$O(1)$ ；返回根节点

Pop ：删去根节点，然后将子节点中最小的提上来，不断递归重复，直到没有比他大的子节点。

Push : 对于一个二叉堆，插入操作一般在叶子节点，但是也有的在root节点。

将新节点作为叶子节点插入；
将该节点上滤（Percolate up）：如果比父节点更小，就不断向上交换。

为了使二叉堆保持平衡，可以使用完全二叉树来表示。 push: 在叶子节点插入，然后上滤；

pop: 弹出根节点。但是问题来了，如果直接从根节点的子节点挑最小然后向上面的 pop 操作一样递归上提，那么就会导致 non-comlete tree！所以我们选择将最近一次插入作为根节点的替补，这样就一定能保证堆的结构还是 complete 的，然后我们再从根节点 percolate down ，使其保持一个堆的性质。P44

上滤还是下滤都是看挑最小的子节点来替换。

对于一个 complete tree ，我们还可以使用数组来存储，因为两者都可以通过广度优先（Breadth First Traversal）进行遍历。

将索引为 0 的位置空出来，对于一个索引为 k 的元素来说：

父节点索引为 $\frac{k}{2}$
子节点索引为 $2k$ 和 $2k+1$ 简单的数学归纳

插入 push 元素并上滤：如果现在数组内有 count 个数，那么插入的元素位置就是 posn=count+1

将位置 posn 的元素与位置 posn/2 的元素进行比较（与父节点比较）；
如果顺序不正确，交换并设置 posn=posn/2，重复上滤操作； P64

pop 操作原理同上，只是将根节点换为最新的节点时执行下滤，看 2k 和 2k+1 P68

时间复杂度分析

Top: $\Theta(1)$
Pop: $O(ln(n))$
Push: $O(ln(n))$ 最好情况 $\Theta(1)$ ，最坏情况 $\Theta(ln(n))$

Binary Max-Heap：最大二叉堆，即根节点为最大值，子树<=父节点

堆排序

堆排序是一个 $\Theta(n \ln(n))$ 的排序算法；基本策略：给定一个包含 $n$ 个对象的无序列表，先将它们放入一个堆中，然后再依次从堆中取出。

使用最小堆：将 $n$ 个对象插入一个最小堆，然后连续取出 $n$ 个对象，它们会按顺序出来。这个取出 $n$ 个对象的操作需要 $O(n \ln(n))$ 的时间。但是，使用最小堆来进行操作会需要额外的一个大小为 n 的堆来存放，这会消耗内存，因此也不是我们想要的 in-place （就地）的算法；

为了实现就地算法，我们可以考虑采用最大堆。

先将 unsorted array 原地转化成一个最大堆，这里要使用堆的数组表示，但是这里没有把 0 空开因此我们的索引计算方式需要发生改变，对于索引为 k 的元素：

父节点为 $\frac{k+1}{2}-1$
子节点为 $2k+1$ 和 $2k+2$

就地堆化（In-Place Heapification） P109

我们从下往上考虑，每个叶子节点都是自己的最大堆；对每一层子树的父节点考虑；
然后一直从右往左，从下往上对每个等级的堆进行“下滤”（将小元素下沉）看图更好理解；
这个交换过程可能需要递归进行，直到该节点下滤到正确的位置。

Heaplify 时间复杂度分析：$\Theta(n)$ P121

数组的就地堆化： P123

第一个非叶子节点的索引为 $\frac{n}{2}-1$ （n为数组长度，最后一个节点，也是叶子节点的索引为 n-1）
然后向前下滤，

131-135 的课件是错的

排序：将最大堆转换成一个排序好的（升序）数组。

当数组被构建成一个最大堆后，堆顶（array[0]）就是最大的元素。
“弹出”最大值：将堆顶元素（最大值）与堆的最后一个元素交换。
放置最大值：交换后，最大的元素就被放置在了数组的末尾，这是它排序后的正确位置。
缩小堆：将堆的大小减 1（即排除掉刚刚放到末尾的那个最大元素）。
恢复堆：由于交换，新的堆顶元素（原先的最后一个元素）可能破坏了最大堆的性质。因此，对新的堆顶（array[0]）执行“下滤”操作，使其在缩小后的堆中恢复最大堆的性质。
重复：重复这个“交换-缩小-下滤”的过程 $n$ 次，直到堆为空。

给出 Gemini 的代码实现：

  
// i 要下滤的子树的根
// n 长度

void percolateDown(int arr[], int n, int i) {
    int largest = i; // 假设根节点 i 是最大的 
    
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 检查左子节点是否在堆范围内，并且是否大于当前最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 检查右子节点是否在堆范围内，并且是否大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果根节点 i 不是最大的节点
    if (largest != i) {
        // 交换根节点和最大的子节点
        std::swap(arr[i], arr[largest]);
        // 交换后，原来的根节点 arr[i] 下降到了索引 largest 的位置
        // 需要递归地对这个新位置进行下滤，以确保子树完全满足最大堆性质
        percolateDown(arr, n, largest);
    }
}

/**
 * @brief 执行堆排序
 *
 * 算法基于文档中的两个主要阶段：
 * 1. 就地堆化 (In-place Heapification)
 * 2. 排序（重复弹出最大元素）
 *
 * @param arr 要排序的数组
 * @param n 数组的大小
 */
void heapSort(int arr[], int n) {
    
    // --- 阶段 1: 构建最大堆 (Heapification) ---
    //
    // 我们从最后一个非叶子节点开始，自底向上调整所有子树
    // 最后一个非叶子节点的索引是 n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        percolateDown(arr, n, i);
    }

    // --- 阶段 2: 排序 ---
    //
    // 循环 n-1 次。
    // 每次循环将当前堆的最大元素（总在堆顶 arr[0]）移动到数组末尾
    for (int i = n - 1; i > 0; i--) {
        
        // 步骤 1: 将堆顶 (arr[0]) 与当前堆的末尾元素 (arr[i]) 交换
        std::swap(arr[0],arr[i]);

        // 步骤 2: 交换后，最大元素已在正确排序位置 (arr[i])
        // 堆的大小缩减为 i (即 0 到 i-1)
        // 步骤 3: 恢复根节点 (arr[0]) 的最大堆性质
        percolateDown(arr, i, 0);
    }
}

int main() {

    int arr[] = {34, 15, 65, 59, 79, 42, 40, 80, 50, 61, 23, 46};
    
    int n = arr.size();
    // 执行堆排序
    heapSort(arr, n);
}

数据结构, 课程笔记

数据结构堆和堆排序

本文由作者按照 CC BY 4.0 进行授权

热门标签