堆

二叉堆是一棵完全二叉树，维护父节点不低于子节点的优先级：最小堆中父值不大于子值，最大堆则相反。极值因此位于根，peek 为 O(1)，插入和 extract_top 的堆调整为 O(log n)，整个结构可放在数组中。

堆只约束上下级，不排列同层节点。像组织图中每人不能高于自己的主管，却不要求同级人员按职位排列。

堆如何工作

数组索引 i 的左右孩子为 2i + 1、2i + 2，父节点为 (i − 1) // 2。完全二叉树除末层外都填满，末层从左向右填，因此数组没有洞，无需额外的树节点链接。

peek 直接读取 data[0]。

insert 先追加到末尾，保持形状完整，再上浮：新值优于父值时交换并上移一层。到索引 0，或遇到不被它超过的父节点时停止。最小堆使用 < 判断是否需要上浮。

extract_top 先保存根值作为返回值，弹出末尾，再把末尾值放到索引 0，向下调整。每层先找两个孩子中优先级更高的一个；它优于当前值才交换，随后进入该子树。没有孩子，或孩子都不更优时停止。用末尾填根避免破坏完全树的形状。

下浮先检查左孩子，再检查右孩子，确定最佳候选后才交换。比较严格，所以左右孩子相等时保留左侧候选。

切换最小堆与最大堆只改变比较器 < / >。画布上方是树，下方是数组，同一次交换同时更新两处。

逐步演示

默认空最小堆，显示容量 10。依次插入 5、3、8、1、9、2，再取出堆顶。

1. insert(5)：放索引 0，i > 0 不成立，无需上浮，得到 [5]。
2. insert(3)：追加到索引 1，3 < 5，交换 arr[1] ↔ arr[0]，得到 [3, 5]。
3. insert(8)：追加到索引 2，父为索引 0，8 ≥ 3，不交换，得到 [3, 5, 8]。
4. insert(1)：先放索引 3，1 < 5，交换 arr[3] ↔ arr[1]，得到 [3, 1, 8, 5]。再因 1 < 3 交换 arr[1] ↔ arr[0]，得到 [1, 3, 8, 5]。两次比较、两次交换，到根停止。
5. insert(9)：位于索引 4，比父 3 大，得到 [1, 3, 8, 5, 9]。
6. insert(2)：位于索引 5，先胜过父 8，交换 arr[5] ↔ arr[2]，再因不小于根 1 而停止。结果 [1, 3, 2, 5, 9, 8]。树根 1，孩子 3、2；3 下方 5、9，2 下方只有 8。
7. extract_top()：返回 1，把末尾索引 5 的 8 移到根并缩短数组，得到 [8, 3, 2, 5, 9]。根的孩子是 3、2，选较小的 2，因 2 < 8 交换 arr[0] ↔ arr[2]，得到 [2, 3, 8, 5, 9]。索引 2 的左孩子索引 5 已越界，停止。新堆顶为第二小的 2。

画布用带实际比较式的虚线连接候选。下浮先给选中的孩子着色，再交换；树和数组同步移动，新值落定时闪绿，取出的根向上离开。

时间与空间复杂度

n 个节点的完全二叉树有 ⌈log₂(n+1)⌉ 层，一次交换最多移动一层。一百万个元素约二十层。数组实现不需要额外的父子指针；若底层动态数组恰好扩容，单次插入还需付出 O(n) 搬迁成本，计入多次插入后仍为摊还 O(log n)。

从已有 n 个元素建堆时，从最后一个内部节点向前下浮，总时间为 O(n)，不是 O(n log n)。大多数节点接近底部，只需很少或无需移动。

边界情况

• 空堆：peek 返回 None，extract_top 抛下溢。空时按钮仍可用，便于观察错误路径。
• 单元素：弹出唯一值后，if self.data: 为假，不执行末尾填根和下浮。
• 重复与平局：最小堆要求 ≤，允许相等。相等的右孩子不会替换左侧候选。
• 显示容量：滑块 4–15，默认 10，只限制画布。超过上限时状态栏说明是显示限制，实际堆受可用存储约束。

常见错误

• 把数组当有序数组。 最终 [2, 3, 8, 5, 9] 中 8 位于 5 前面，仍是合法堆。逐个取极值才得到排序输出，这是堆排序的基础。
• 下浮选错孩子。 最小堆若与较大孩子交换，较小孩子可能仍违反父子顺序。先选最优孩子，再比较、交换。
• 混用索引公式。 0 起始用 2i + 1、2i + 2、(i − 1) // 2；1 起始用 2i、2i + 1、i // 2，不能混搭。
• 期待快速任意值搜索。 堆不规定非极值在哪，最坏搜索 O(n)。按键查询或有序范围查询更适合平衡 BST。
• 随意翻转比较器。 < 改为 > 会改变极值方向。结构仍可能合法，但调用者的排序预期已失效。