理解二叉堆：堆排序与入堆操作

"本文主要介绍了堆排序中的关键操作——入堆代码，并讲解了二叉堆的概念，包括完全二叉树的定义以及堆的性质。通过示例代码详细阐述了入堆过程，即如何将新元素添加到堆中并保持堆的特性。" 堆排序是一种基于比较的排序算法，其核心数据结构是二叉堆。二叉堆是一种特殊的完全二叉树，分为两种类型：小根堆和大根堆。在小根堆中，每个节点的值都小于或等于其子节点的值，而大根堆则相反，每个节点的值大于或等于其子节点的值。这种性质使得堆可以高效地实现优先队列的功能，例如在最短路径计算、事件驱动模拟等场景中广泛应用。 完全二叉树是二叉堆的基础，它的特点是除了最后一层外，每一层都被完全填充，且所有节点尽可能地靠左排列。由于堆可以用一维数组来表示，因此可以通过数组下标计算出节点的父节点和子节点的位置。例如，节点i的父节点位置为`trunc(i/2)`，左子节点为`2i`，右子节点为`2i+1`。 入堆操作是将一个新的元素插入到堆中，通常是在堆的末尾插入，然后通过一系列比较和交换，确保新的堆仍然满足堆的性质。入堆的过程可以用`sinkup`函数来实现，该函数会从插入节点开始，逐级与其父节点比较，如果当前节点的值大于其父节点，则交换两者，然后继续向上更新，直到找到合适的位置或者到达堆的根节点。以下是`sinkup`函数的大致代码： ```pascal procedure sinkup(i: longint); var parent, tmp: longint; begin parent := i shr 1; if (heap[parent] < heap[i]) then // 对于大根堆，此处应为heap[parent] > heap[i] begin tmp := heap[i]; heap[i] := heap[parent]; heap[parent] := tmp; if (parent > 1) then sinkup(parent); // 如果不是根节点，继续向上更新 end; end; ``` 在实际的`pushheap`入堆过程中，首先会增加堆的长度，表示添加了一个新的元素，然后调用`sinkup`函数来维护堆的性质： ```pascal procedure pushheap(x: longint); begin inc(length); heap[length] := x; if (length > 1) then sinkup(length); end; ``` 通过这样的方式，我们可以保证每次插入新元素后，堆依然保持有序性，从而可以在O(log n)的时间复杂度内完成出队（删除最小或最大元素）和入队（插入新元素）的操作，这使得堆排序在处理大规模数据时具有较高的效率。在堆排序算法中，除了入堆操作外，还包括建堆、调整堆以及反复提取堆顶元素等步骤，这些步骤共同构成了完整的排序过程。