题目重点：从完全二叉树下标推导push/pop，不借助库堆，解释选择更小孩子与单元素pop。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 零下标数组，父节点(i−1)//2、孩子2i+1和2i+2；没有右孩子时只看左孩子。
- 存可比较的整数、重复值允许；pop返回最小值，空堆抛IndexError。
- 本文实现push/pop，不把有序数组或BST当作二叉堆。若需任意删除或decrease-key还要索引合同。
解题路线
- 堆序是每个父值≤孩子值，不是整个数组升序。数组天然表示完整二叉树，只要尾部插入/删除就保留形状，无需为每个节点分配对象。
- push把新值加在末尾。唯一可能破坏堆序的是它与父节点的边；若更小就交换并沿父方向继续，其他子树没有变化。走到根或父≤子即停。
- pop保存根，把尾值移到根，末尾删除保持完全性。只可能违反根向下的某条边；选两个孩子中更小者，否则可能交换后仍大于另一个孩子。
- 下沉时如果父≤较小孩子，就也≤另一个孩子，整棵局部子树已满足堆序；交换后小孩子升至父位置正确，尾值继续下移直到叶。这个不变量解释为何一次pop只沿一条路径。
- 单元素pop在取last后数组已空，不能再赋a[0]。空堆先检查；相同值无需交换，能减少动作且不影响正确性。两个元素情形专门覆盖“只有左孩子”。
- 批量建堆自底向上heapify可O(n)，而n次push是O(n log n)。底层有很多低高度节点，总下沉工作按高度加权收敛；不要把根的最大高度乘所有节点当heapify成本。
手动走一遍
依次push 5、2、4、1，最终某个合法数组[1,2,4,5]。pop1后尾5补根，孩子2/4中选2交换，得到[2,5,4]，数组不是升序仍是合法堆。再逐个pop必须得到2、4、5。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Array-backed min heap. Empty pop raises IndexError."""
class MinHeap:
def __init__(self):
self.data = []
def push(self, value):
a = self.data
a.append(value)
i = len(a) - 1
while i:
p = (i - 1) // 2
if a[p] <= a[i]:
break
a[p], a[i] = a[i], a[p]
i = p
def pop(self):
a = self.data
if not a:
raise IndexError("empty heap")
answer = a[0]
last = a.pop()
if a:
a[0] = last
i = 0
while 2 * i + 1 < len(a):
child = 2 * i + 1
if child + 1 < len(a) and a[child + 1] < a[child]:
child += 1
if a[i] <= a[child]:
break
a[i], a[child] = a[child], a[i]
i = child
return answer
复杂度
push/pop最坏O(log n)，动态数组append可能偶发O(n)扩容，摊销插入仍O(log n)；空判断O(1)，空间O(n)。真正硬实时场景可预分配容量并另定溢出策略。
易错点与追问
容易失分的边界
- 把孩子写成2n+1而不是2i+1。
- 下沉随便选一个孩子。
- 只有一个元素仍写a[0]。
- 误把数组升序作为堆验收条件。
继续深挖
- 怎样线性heapify？
- 若要稳定处理相同优先级怎么加序号？
- 带decrease-key需要哪份索引？
- 怎样实现max heap而保持同一证明？
