数据结构与算法 / 系统课时

堆的插入与删除

堆的插入与删除

堆的核心操作只有两类:插入元素时向上恢复堆序,删除堆顶时向下恢复堆序。本课以最小堆为主线,完成可运行实现,并说明为什么单次操作是 O(log⁡n)O(\log n)、自底向上建堆是 O(n)O(n)。

学习目标

  • 掌握插入上浮、堆顶删除和下沉的完整过程
  • 正确处理空堆、单元素堆和双子节点选择
  • 分析插入、删除与批量建堆的时间复杂度

堆结构与操作机制

最小堆是一棵完全二叉树,每个节点都不大于它的子节点,因此堆顶始终保存最小值。使用从 0 开始的数组存储时,下标为 i 的节点关系如下:

  • 父节点:(i - 1) // 2
  • 左子节点:2 * i + 1
  • 右子节点:2 * i + 2

完全二叉树保证新节点总能追加到数组末尾,删除堆顶后也可以用末尾元素补到根节点,不需要移动整段数组。

最小堆插入与删除过程

插入时,新元素只可能破坏它到根节点这条路径上的堆序。把元素放到末尾后,只要它小于父节点,就交换并继续向上;遇到不大于它的父节点或到达根节点时停止。

删除堆顶时,先保存根值,再弹出数组末尾元素。若堆仍非空,就用该元素替换根节点。下沉时必须比较左右子节点,并选择其中较小者交换;若当前节点已经不大于较小子节点,堆序恢复。

两种过程最多经过树高,完全二叉树高度为 O(log⁡n)O(\log n),所以单次插入和删除堆顶都是 O(log⁡n)O(\log n)。仅查看堆顶不修改结构,复杂度为 O(1)O(1)。

完整实现

下面的实现同时提供 push、pop、peek 和自底向上的 heapify。heapify 从最后一个非叶子节点开始下沉,虽然单次下沉最坏为 O(log⁡n)O(\log n),但多数节点靠近叶子,总代价为 O(n)O(n)。

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 时应明确抛出异常,而不是返回一个可能与合法元素冲突的特殊值。只有一个元素时,弹出末尾后数组已空,不再执行补根和下沉。

下沉不能固定选择左子节点。右子节点更小时,如果仍与左子节点交换,局部堆序可能继续错误。另一个常见问题是交换后没有更新当前下标,导致后续比较从旧位置继续。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

堆的插入与删除

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通