堆和优先队列的关系

这是一个非常经典且核心的计算机科学概念问题。一言以蔽之：优先队列（Priority Queue）是逻辑接口（ADT），而堆（Heap）是实现这个接口最高效的物理数据结构。

它们的关系可以类比为 “接口（Interface）” 与 “实现类（Implementation）” 的关系，或者 “汽车（功能）”与 “发动机（核心组件）”的关系。

优先队列 (Priority Queue) —— 逻辑层 (ADT)

定义：它是一种抽象数据类型 (Abstract Data Type, ADT)。它定义了数据的行为，而不是数据的存储方式。
规则：普通的队列是“先进先出”（FIFO），而优先队列是“优先级最高的先出”。
核心操作：

1. insert(item, priority): 插入一个带优先级的元素。
2. deleteMax() 或 deleteMin(): 取出并删除优先级最高（或最低）的元素。
3. peek(): 查看优先级最高的元素。

堆 (Heap) —— 物理层 (Data Structure)

定义：它是一种具体的数据结构。通常指二叉堆 (Binary Heap)，本质上是一种完全二叉树，但通常用数组来实现。
规则（堆性质）：
- 大顶堆 (Max-Heap)：任意节点的值 \(\ge\)其子节点的值。
- 小顶堆 (Min-Heap)：任意节点的值 \(\le\) 其子节点的值。
作用：它专门为了快速找到最大值或最小值而设计。

关系解析：

算法使用优先队列：例如，Dijkstra 算法说：“我需要一个能每次给我当前距离最短节点的容器”。这个容器就是优先队列。
优先队列依赖堆：为了让 Dijkstra 算法跑得快，优先队列不能用普通的数组实现（太慢），必须用堆来实现。

295. 数据流的中位数

题目

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

-10⁵ <= num <= 10⁵
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10⁴ 次调用 addNum 和 findMedian

题解

使用两个优先队列 queMax 和 queMin 来维护数据流，使得我们可以在 \(O(1)\) 时间内找到中位数，在 \(O(\log N)\) 时间内添加新数字。

为了找到中位数，我们将所有数字分成两半：

较小的一半：存放在 max_heap（大顶堆）中。
较大的一半：存放在 min_heap（小顶堆）中。

维持平衡的规则：

我们要保证 max_heap 的元素数量等于或者比 min_heap 多 1 个。
这样，中位数要么是 max_heap 的堆顶（总数为奇数时），要么是两个堆顶的平均值（总数为偶数时）。

当我们尝试添加一个数 num 到数据结构中，我们需要分情况讨论：

两个堆大小相等

目标：让 max_heap 多一个元素（因为我们要把 max_heap 维持得稍微大一点点）。此时，不能直接把 num 放进 max_heap，因为 num 可能很大，属于“较大的一半”。

1. 先把 num 放进 min_heap（较大半），让 min_heap 自动排序。
2. 把 min_heap 里最小的那个吐出来
3. 把吐出来的这个数（它是较大半里最小的，或者就是 num 自己），放进 max_heap。

max_heap 比 min_heap 多一个

目标：让两个堆大小重新相等，此时，要把一个数移给 min_heap。

1. 先把 num 放进 max_heap。
2. 把 max_heap 里最大的那个吐出来。
3. 放进 min_heap。

特别地，当累计添加的数的数量为 0 时，我们将 num 添加到 queMin 中。

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        if len(self.max_heap) == len(self.min_heap):
            heapq.heappush(self.max_heap, - heapq.heappushpop(self.min_heap, num))
        else:
            heapq.heappush(self.min_heap, - heapq.heappushpop(self.max_heap, -num))

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (- self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return - self.max_heap[0]

#

!

堆和优先队列的关系

295. 数据流的中位数

题目

题解