完全二叉堆

完全二叉堆

逻辑上等同于完全二叉树，物理上用向量实现。 堆序性：处处满足 H[i] <= H[Parent(i)]，根节点为最大值

• 与数据结构-二叉搜索树不同，只有偏序关系，没有全序关系 内部节点的最大秩为 $\lfloor \frac{n-2}{2}\rfloor$

插入

插入到向量末尾（完全二叉树底层），检查和父亲的大小关系

• 若父亲更大或已经是根，结束插入
• 若父亲更小，交换（此时兄弟的堆序性也可以保证） 只可能与父亲节点交换并上升一层，最多上升 $O(\log n)$ 层，时间复杂度为 $O(\log n)$ 从期望角度上讲，时间复杂度为 $O(1)$

删除

将向量末尾的元素替换到首位，向下检视孩子和自身的大小关系

• 若比两个孩子都大，结束
• 若比其中之一小，与这个孩子交换，重复
• 若比两个孩子都小，与其中较大者交换，重复 最多下降 $O(\log n)$ 层，时间复杂度为 $O(\log n)$ 数学期望也为 $O(\log n)$

建堆

自上而下的上滤

逐个遍历，并视为插入。 时间复杂度为 $O(n\log n)$ 此时花了 $O(n\log n)$ 的时间得到偏序关系，而本可以通过排序得到全序关系，必然可以优化……

自下而上的下滤

Floyd 建堆法：

Floyd 建堆法

将叶子节点视为含有单个元素的堆，自下而上地下滤，每次合并两个堆。 每个内部节点的调整时间正比于高度而非深度。 时间复杂度为 $O(n)$

Link to original

堆排序

在选择排序中，如果用堆替代向量，可以在 $O(\log n)$ 内找到前缀的最大值，总时间复杂度为 $O(n\log n)$ 每次只需将首元素和当前末元素交换并执行下滤。