二叉堆虽然带着“树”的名字，但多数实现都使用数组完成。它是一棵完全二叉树，并且每个父节点与子节点之间保持严格的大小关系。以最小堆为例，父节点的值总是不大于它的两个子节点，这样堆顶就稳定地保存了当前集合中的最小值。最大堆则相反。由于完全二叉树的结构非常规整，二叉堆不需要使用指针来表示左右子树，直接用数组下标就能快速定位父子关系。
在实际编码中，如果根节点的下标设为0，那么对于任意位置i的元素，它的左孩子位于2*i+1，右孩子位于2*i+2，父节点位于(i-1)//2。这个映射关系是插入和删除操作的基础。
一、二叉堆的结构性质与数组映射
二叉堆首先是一棵完全二叉树。完全二叉树意味着除了最后一层外，其他每一层都被节点填满，而且最后一层的节点都靠左排列。这个限制看起来严格，但它带来的好处非常直接：完全二叉树可以一层一层顺序写进数组，而不会浪费数组空间，也不需要使用指针来记录左右子树。
除了完全二叉树的结构约束，二叉堆还必须满足堆序性质。以最小堆为例，任意一个父节点的值都小于或等于其子节点的值；最大堆则要求父节点的值大于或等于子节点的值。注意，堆序只约束父子之间的大小关系，并不要求左右孩子之间有序。例如数组[1,4,2,7,8,5]表示一个最小堆：根节点是1，左孩子是4，右孩子是2，4的孩子是7和8，2的孩子是5。左孩子4和右孩子2之间没有大小顺序要求。
数组下标从0开始时，父节点与子节点的位置计算非常轻量。对下标i来说，父节点是(i-1)//2，左孩子是2*i+1，右孩子是2*i+2。因此判断某个节点是否有父节点，只需要检查i是否大于0；判断某个节点是否有左孩子，只需要检查2*i+1是否小于堆的当前长度。这种数组映射避免了树节点对象和指针维护成本，也让插入和删除只需交换数组元素即可完成结构调整。
二、插入操作：追加到末尾再上浮
向二叉堆插入一个新元素时，第一步并不是直接放到逻辑上正确的位置，而是先把新元素追加到数组末尾。这样做的好处是，完全二叉树的结构约束不会在插入瞬间被破坏：末尾位置正好是当前完全二叉树下一层最靠左的空位，或者新开一层的最左位置。
但新元素放在末尾后，很可能违反堆序性质。例如向一个最小堆中插入一个很小的值，它可能比自己的父节点还小。此时就需要执行上浮操作，也就是让这个新元素沿着父节点方向逐步向上移动。具体过程是：比较当前节点和父节点的值，如果当前节点小于父节点，就交换两者，然后继续从父节点位置向上比较；如果当前节点不小于父节点，或者已经到达根节点，上浮就结束了。每一轮交换都会把新元素向上提升一层，因此最多经过树高次交换，堆序就能恢复。
下面的代码使用数组实现最小堆的插入和上浮逻辑，索引从0开始：
def heap_insert(heap, value):
heap.append(value)
sift_up(heap, len(heap) - 1)
def sift_up(heap, idx):
# 从 idx 位置开始向上调整，直到堆序恢复
while idx > 0:
parent = (idx - 1) // 2
if heap[idx] < heap[parent]:
heap[idx], heap[parent] = heap[parent], heap[idx]
idx = parent
else:
break
heap_insert先把值追加到数组末尾，然后从末尾位置开始上浮。sift_up中的循环条件idx > 0确保不会访问根节点的父节点。每次比较都使用最小堆的小于关系，如果当前节点比父节点更小，就交换位置。由于树的高度是O(log n)，插入操作的时间复杂度也是O(log n)。当堆中元素特别多时，相比线性扫描再插入的数组方案，优势非常明显。
三、删除操作：堆顶补位再下沉
二叉堆的删除通常指的是删除堆顶元素，因为堆顶保存的是最小堆中的最小值或最大堆中的最大值。如果直接把根节点移走，整棵树会分裂成左右两棵子树，结构被破坏，重新合并成本很高。常规做法是：先记录根节点的值作为返回值，然后取出数组最后一个元素，将它放到根位置，再删除数组末尾。这样完全二叉树的结构仍然成立，但堆序可能被破坏。
接下来需要执行下沉操作。下沉的方向与上浮相反，是从根节点向子节点方向调整。以最小堆为例，每次先找到当前节点的左右孩子中值较小的那个，然后把当前节点与这个较小子节点比较。如果当前节点比较大，就交换两者，并继续从交换后的子节点位置向下调整；如果当前节点已经不大于较小子节点，或者当前节点已经没有孩子，下沉就结束了。下沉操作会沿着树的高度逐层下移，最多经过O(log n)次比较和交换。
下面给出删除堆顶和下沉调整的代码，仍然使用数组和最小堆：
def heap_pop(heap):
if not heap:
raise IndexError('heap is empty')
root = heap[0]
last = heap.pop()
if heap:
heap[0] = last
sift_down(heap, 0)
return root
def sift_down(heap, idx):
n = len(heap)
while True:
smallest = idx
left = 2 * idx + 1
right = 2 * idx + 2
if left < n and heap[left] < heap[smallest]:
smallest = left
if right < n and heap[right] < heap[smallest]:
smallest = right
if smallest != idx:
heap[idx], heap[smallest] = heap[smallest], heap[idx]
idx = smallest
else:
break
在heap_pop中，last = heap.pop()会删除并返回末尾元素。如果删除末尾后堆不为空，就把这个元素放到根位置，然后从根开始下沉。sift_down先假设当前节点是最小的，然后分别检查左右孩子，更新最小值的下标。如果最小值下标不再是当前节点，就交换并继续下沉；否则说明堆序已经恢复，直接退出循环。
这个下沉过程有一个容易出错的地方：必须同时判断孩子是否存在。代码中的left < n和right < n就是防止访问越界。另一个细节是，选择左右孩子中较小者，而不是随意拿一个孩子比较，这样才能保证交换后父节点一定不大于两个子节点，避免遗漏违反堆序的情况。
四、复杂度对比与典型应用
二叉堆最大的优势在于插入和删除堆顶都能保持在O(log n)，同时查找最值只需要O(1)。如果使用无序数组，插入虽然可以O(1)完成，但删除最值需要扫描整个数组，复杂度为O(n)；如果使用有序数组，删除最值很快，但插入时需要移动大量元素，复杂度同样是O(n)。二叉堆在插入和删除之间取得了很好的平衡，因此特别适合需要频繁获取最值的动态集合。
| 数据结构 | 插入 | 删除堆顶 | 查找最值 |
|---|---|---|---|
| 无序数组 | O(1) | O(n) | O(n) |
| 有序数组 | O(n) | O(1) | O(1) |
| 二叉堆 | O(log n) | O(log n) | O(1) |
这种特性让二叉堆成为优先队列的常见实现方式。任务调度器中，优先级最高的任务需要最先被取出；图算法如Dijkstra中，每次都要选择当前距离最小的节点；维护一个动态数据流的Top K元素时，可以使用一个大小为K的最小堆，堆顶始终是当前第K大的元素。这些都是二叉堆插入和删除操作的直接应用。
实现二叉堆时，还需要注意最大堆和最小堆只是比较符号不同。把代码中所有小于号改成大于号，就能得到最大堆。另一个常见问题是索引从0开始还是从1开始：如果从1开始存储，父节点下标是i//2，左孩子是2*i，右孩子是2*i+1，计算上略有差异。无论采用哪种方式，只要插入时保持完全二叉树结构，删除时先用末尾补位，再通过上浮或下沉恢复堆序，就能得到稳定可靠的二叉堆实现。