数据结构与算法 / 系统课时
堆的插入与删除
堆的插入与删除
堆的核心操作只有两类:插入元素时向上恢复堆序,删除堆顶时向下恢复堆序。本课以最小堆为主线,完成可运行实现,并说明为什么单次操作是 、自底向上建堆是 。
学习目标
- 掌握插入上浮、堆顶删除和下沉的完整过程
- 正确处理空堆、单元素堆和双子节点选择
- 分析插入、删除与批量建堆的时间复杂度
堆结构与操作机制
最小堆是一棵完全二叉树,每个节点都不大于它的子节点,因此堆顶始终保存最小值。使用从 0 开始的数组存储时,下标为 i 的节点关系如下:
- 父节点:
(i - 1) // 2 - 左子节点:
2 * i + 1 - 右子节点:
2 * i + 2
完全二叉树保证新节点总能追加到数组末尾,删除堆顶后也可以用末尾元素补到根节点,不需要移动整段数组。

插入时,新元素只可能破坏它到根节点这条路径上的堆序。把元素放到末尾后,只要它小于父节点,就交换并继续向上;遇到不大于它的父节点或到达根节点时停止。
删除堆顶时,先保存根值,再弹出数组末尾元素。若堆仍非空,就用该元素替换根节点。下沉时必须比较左右子节点,并选择其中较小者交换;若当前节点已经不大于较小子节点,堆序恢复。
两种过程最多经过树高,完全二叉树高度为 ,所以单次插入和删除堆顶都是 。仅查看堆顶不修改结构,复杂度为 。
完整实现
下面的实现同时提供 push、pop、peek 和自底向上的 heapify。heapify 从最后一个非叶子节点开始下沉,虽然单次下沉最坏为 ,但多数节点靠近叶子,总代价为 。
python
class MinHeap:
def __init__(self, values=None):
self.items = list(values or [])
self._heapify()
def _heapify(self):
# 叶子节点天然满足堆序,只处理最后一个非叶子节点及其祖先。
for index in range(len(self.items) // 2 - 1, -1, -1):
self._sift_down(index)
def _sift_down(self, index):
size = len(self.items)
while True:
left = 2 * index + 1
right = 2 * index + 2
smallest = index
if left < size and self.items[left] < self.items[smallest]:
smallest = left
if right < size and self.items[right] < self.items[smallest]:
smallest = right
if smallest == index:
return
self.items[index], self.items[smallest] = (
self.items[smallest],
self.items[index],
)
index = smallest
def push(self, value):
self.items.append(value)
index = len(self.items) - 1
# 新元素只需沿祖先链上浮,不会影响其他分支。
while index > 0:
parent = (index - 1) // 2
if self.items[parent] <= self.items[index]:
return
self.items[parent], self.items[index] = (
self.items[index],
self.items[parent],
)
index = parent
def pop(self):
if not self.items:
raise IndexError("heap is empty")
root = self.items[0]
last = self.items.pop()
if self.items:
self.items[0] = last
self._sift_down(0)
return root
def peek(self):
if not self.items:
raise IndexError("heap is empty")
return self.items[0]
heap = MinHeap([7, 3, 9, 1, 5])
print("建堆后:", heap.items)
heap.push(2)
print("插入 2:", heap.items)
print("堆顶:", heap.peek())
print("依次出堆:", [heap.pop() for _ in range(6)])预期输出:
text
建堆后: [1, 3, 9, 7, 5]
插入 2: [1, 3, 2, 7, 5, 9]
堆顶: 1
依次出堆: [1, 2, 3, 5, 7, 9]同一组元素可能形成不同但都合法的堆;本示例的输出由固定的建堆和交换顺序决定。
边界、易错点与复杂度
空堆执行 pop 或 peek 时应明确抛出异常,而不是返回一个可能与合法元素冲突的特殊值。只有一个元素时,弹出末尾后数组已空,不再执行补根和下沉。
下沉不能固定选择左子节点。右子节点更小时,如果仍与左子节点交换,局部堆序可能继续错误。另一个常见问题是交换后没有更新当前下标,导致后续比较从旧位置继续。
按自己的节奏,确认真正理解。