上一页认识了完全二叉堆的形状，但光有形状还不够——节点之间得讲「规矩」。想象一家公司：上级的能力必须不弱于直接下属，否则组织就乱套了。堆的这条规矩，就叫堆序性。

上层是树形结构，实线箭头 2i+1、2i+2 指向孩子；虚线箭头标出父亲下标的换算，物理上它们连续存进一个向量。

插入一个新元素，靠三步既保住完全二叉的形，又保住堆序。

上一步我们把新元素直接追加到向量末尾——这是完全二叉树唯一能放的位置。但这个新来的可能比父节点还大，堆序被破坏了。怎么办？先看看它在树里和父亲的关系。

两版上滤结果相同，但赋值开销差三倍——混淆点在于以为比较次数也变了。

把 5 插入堆 [2,4,6,7]，逐帧跟踪上滤的每一步。

insert 与 percolateUp 的真实实现，逐行对照前面的三步走与整体上滤。

L1/L2 对应三步走的前两步；L4 是向量存储下的父结点下标公式；L5 是循环不变式出口——父亲更大即堆序恢复；L7 完成「整体上移」。

上一页我们逐行走完了上滤代码，循环里其实藏着一个问题：交换到什么时候才算完？理解了终止条件，边界情况——比如新元素一路顶到根——也就迎刃而解了。

前面我们走完了一遍插入：新元素从叶一路向上滤，直到找到位置。那这条路最长能有多长？答案藏在这棵树的高度里——而完全二叉树的高度，恰好是对数级的。

向含 15 个元素的完全二叉堆插入一个新元素，上滤最坏需要与父亲交换几次？

• ✓堆序性只需父子成立，兄弟无序——这是插入能局部修复的前提
• ✓向量按层序存完全二叉树，下标 i 的父亲是 ⌊(i−1)/2⌋，无需指针
• ✓插入三步：接到末尾、与父亲比较、必要时上滤
• ✓整体上滤优于逐次交换：比较次数不变，赋值从 3t 降到 t+1
• ✓树高 O(logn) 封顶，单次插入最坏 O(logn)

先自己想一会儿，再对照参考答案——想不通的地方，值得回去翻对应那页。