T11 堆的上滤与下滤 比较次数

T11_堆排序_初始堆的构造过程

T11 堆排序 初始堆的构造过程

• 建堆 ($O(n)$)：从最后一个非叶子结点开始，自底向上依次对每个非叶子结点进行下滤操作，直到根结点。
• 排序 ($O(n\log n)$，调整 $n-1$ 次，每次下滤 $O(\log n)$)：将堆顶元素与堆的最后一个元素交换，接下来将堆的大小减 1，对新的堆顶元素进行下滤操作 (自上向下)，重复此过程直到堆的大小为 1。
• 删除堆顶元素：将堆顶元素与堆的最后一个元素交换，堆的大小减 1，对新的堆顶元素进行下滤操作。

下滤操作：将当前结点与其子结点中较小的一个进行比较 (比较 2 次，子结点比较找较小的，较小的与当前结点比较), 若当前结点大于该子结点，则交换位置，继续对交换后的子结点进行下滤, 直到当前结点小于等于其子结点或到达叶子结点为止。

• 仅在修改键值 (小根堆减小，大根堆增大) 时需要上滤操作。

Link to original