28 | 堆和堆排序：为什么说堆排序没有快速排序快

在讲堆排序建堆的时候，我说到，对于完全二叉树来说，下标从 2n+1 到 n 的都是叶子节点，这个结论是怎么推导出来的呢？

对于完全二叉树来说，下标从 n/2+1 到 n 的节点都是叶子节点的结论是基于完全二叉树的性质推导得到的。完全二叉树的性质包括：

1. 父节点和子节点的关系： 对于下标为 i 的节点，其左子节点的下标为 2i，右子节点的下标为 2i+1。反之，对于下标为 j 的节点，其父节点的下标为 j/2。

2. 从上到下，从左到右填充节点： 在完全二叉树中，从上到下、从左到右依次填充节点，直到最后一层。最后一层的节点可能不是满的，但是填充时是从左到右填充的。

基于这两个性质，我们可以推导出下标从 n/2+1 到 n 的节点都是叶子节点：

• 对于下标为 i 的节点，如果 i > n/2，则 2i > n，即左子节点的下标超过了 n。因此，大于 n/2 的节点没有左子节点。

• 右子节点的下标为 2i+1，当 i > n/2 时，2i+1 > n+1，即右子节点的下标超过了 n。因此，大于 n/2 的节点没有右子节点。

因此，结论是下标从 n/2+1 到 n 的节点都是叶子节点。在堆排序中，这个性质是建堆过程中的一个重要观察点，因为我们在建堆时只需要考虑非叶子节点的调整，而不必关心叶子节点。

我们今天讲了堆的一种经典应用，堆排序。关于堆，你还能想到它的其他应用吗？

1. 优先队列： 堆可以用于实现优先队列，其中每个元素都有一个关联的优先级。堆的根节点通常是具有最高（或最低）优先级的元素，因此可以在 O(1)时间内找到和删除最高优先级的元素。

2. 调度器和任务管理： 在操作系统中，堆可以用于实现任务调度器。每个任务的优先级对应于堆中的元素，系统可以选择执行优先级最高的任务。

3. 图算法： 堆可以用于实现图算法中的 Dijkstra 算法和 Prim 算法。在这些算法中，堆用于快速找到图中的最短路径或最小生成树。

4. 中位数维护： 堆可以用于实时计算数据流的中位数。通过将数据流一分为二，并在两个堆之间保持平衡，可以在 O(1)时间内找到中位数。

5. 哈夫曼编码： 堆结构被广泛用于哈夫曼编码，用于数据压缩。

6. 内存管理： 在一些动态内存分配的系统中，堆被用来管理和分配内存块。