优先队列与最小堆

优先队列是一种特殊的队列，每次取出的元素总是“最优先”的那个。最小堆是实现优先队列的常用方法，能高效地找到最小值。下面带你轻松了解最小堆的原理和用法！

什么是优先队列和最小堆？

普通队列是“先进先出”，而优先队列是“优先级高的先出”。最小堆是一种二叉树结构，能保证每次取出的都是最小值。

生活化类比：
比如医院挂号，急诊病人优先就诊；或者抢座位时，最着急的人先抢到座位。

最小堆结构示意图：

最小堆的常用操作

插入：把新元素放到堆的最后，然后“上浮”到合适位置。
取最小：最小值总在堆顶，直接取出。
删除最小：把堆顶元素删除，用最后一个元素补上，然后“下沉”到合适位置。

最小堆可视化演示


# 完全二叉树简介：
# 完全二叉树是一种特殊的二叉树结构，除了最后一层外，每一层的节点数都达到最大，最后一层的节点都集中在左侧。
# 这种结构保证了树的高度最小，便于用数组顺序存储，父子节点下标有简单的数学关系。
# 最小堆正是利用完全二叉树的结构高效实现的。
# 算法执行原理：
# 最小堆是一种完全二叉树结构，能高效维护一组元素的最小值。
# 插入元素时，将新元素放到堆尾，然后不断与父节点比较并“上浮”，直到满足父节点小于等于自己的最小堆性质。
# 弹出最小值时，将堆顶元素移除，用最后一个元素补到堆顶，然后不断与子节点比较并“下沉”，直到满足最小堆性质。
# 这样可以保证每次取出的都是当前所有元素中的最小值，插入和删除的时间复杂度都是O(log n)。

# 定义最小堆类
class MinHeap:
    # 初始化方法，创建一个空列表用于存储堆元素
    def __init__(self):
        self.data = []

    # 向堆中插入新元素
    def push(self, val):
        # 将新元素添加到堆的末尾
        self.data.append(val)
        # 获取新元素的索引
        i = len(self.data) - 1
        # 上浮操作，保证最小堆性质
        while i > 0:
            # 计算父节点索引
            parent = (i - 1) // 2
            # 如果当前节点小于父节点，则交换
            if self.data[i] < self.data[parent]:
                self.data[i], self.data[parent] = self.data[parent], self.data[i]
                # 更新索引为父节点，继续上浮
                i = parent
            else:
                # 如果不需要交换，结束上浮
                break

    # 弹出堆顶元素（最小值）
    def pop(self):
        # 如果堆为空，返回None
        if not self.data:
            return None
        # 记录堆顶元素
        min_val = self.data[0]
        # 弹出最后一个元素
        last = self.data.pop()
        # 如果堆不为空，将最后一个元素放到堆顶，并下沉调整
        if self.data:
            self.data[0] = last
            i = 0
            n = len(self.data)
            # 下沉操作，保证最小堆性质
            while True:
                # 计算左子节点索引
                left = 2 * i + 1
                # 计算右子节点索引
                right = 2 * i + 2
                # 记录当前最小值索引
                smallest = i
                # 如果左子节点存在且小于当前节点，更新最小值索引
                if left < n and self.data[left] < self.data[smallest]:
                    smallest = left
                # 如果右子节点存在且小于当前最小值，更新最小值索引
                if right < n and self.data[right] < self.data[smallest]:
                    smallest = right
                # 如果最小值索引没有变化，结束下沉
                if smallest == i:
                    break
                # 交换当前节点与最小子节点
                self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
                # 更新索引为最小子节点，继续下沉
                i = smallest
        # 返回堆顶元素
        return min_val

# 使用示例
# 创建最小堆对象
heap = MinHeap()
# 向堆中依次插入元素5, 2, 8, 1
for x in [5, 2, 8, 1]:
    heap.push(x)
# 打印当前堆的内容，应该为[1, 2, 8, 5]
print(heap.data)  # 输出[1, 2, 8, 5]
# 弹出堆顶元素（最小值），应该为1
print(heap.pop())  # 输出1
# 打印弹出后的堆内容，应该为[2, 5, 8]
print(heap.data)  # 输出[2, 5, 8]

创建最小堆对象： heap = MinHeap()
此时堆为空：[]
插入5： heap.push(5)
5加入堆尾，无需上浮，堆为：[5]
插入2： heap.push(2)
2加入堆尾，与父节点5比较，2更小，上浮到堆顶，堆为：[2, 5]
插入8： heap.push(8)
8加入堆尾，与父节点2比较，8更大，无需上浮，堆为：[2, 5, 8]
插入1： heap.push(1)
1加入堆尾，与父节点5比较，1更小，交换到父节点位置，再与新父节点2比较，1更小，再次上浮到堆顶，堆为：[1, 2, 8, 5]
打印堆内容： print(heap.data)
输出：[1, 2, 8, 5]
弹出最小值： heap.pop()
堆顶1被弹出，最后一个元素5补到堆顶，与左右子节点2、8比较，2最小，5与2交换，下沉到合适位置，堆为：[2, 5, 8]
打印堆内容： print(heap.data)
输出：[2, 5, 8]

每一步都严格按照最小堆的“上浮”与“下沉”规则，保证堆顶始终是最小值。

应用场景

Dijkstra算法
每次优先处理距离最近的节点。

任务调度
优先处理最紧急的任务。

实时排行榜
快速维护前N名。

数据流TopK
大数据场景下找出最小/最大K个元素。

总结

最小堆让我们能高效地管理和获取“最小值”，是很多算法和系统的基础工具。学会它，你就能轻松应对各种优先级相关的问题！