堆（题单顺序）

本页包含题单「堆」分组的全部题目，顺序与 list.json 保持一致。

堆题统一“选型口诀”（点击展开）

Top K 最大：用“小根堆”保留 k 个（堆顶是第 k 大）。
Top K 最小：用“大根堆”保留 k 个（堆顶是第 k 小）。
中位数维护：左边大根堆 + 右边小根堆，保持尺寸差不超过 1。
存什么：需要比较时就把比较键（值/频次/距离）放到堆的 comparator 里，堆里通常存“元素本体或下标”。

215. 数组中的第 K 个最大元素

力扣原题：215. 数组中的第K个最大元素

Medium

数组

分治

快速选择

排序

堆（优先队列）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

最优解（小根堆保留 k 个最大：堆顶就是第 k 大）

正在加载编辑器...

Rust 参考（点击展开）

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn find_kth_largest(nums: Vec<i32>, k: usize) -> i32 {
    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for x in nums {
        heap.push(Reverse(x));
        if heap.len() > k { heap.pop(); }
    }
    heap.peek().unwrap().0
}

fn main() {
    println!("{}", find_kth_largest(vec![3,2,1,5,6,4], 2));       // 5
    println!("{}", find_kth_largest(vec![3,2,3,1,2,4,5,5,6], 4)); // 4
    println!("{}", find_kth_largest(vec![1], 1));                  // 1
    println!("{}", find_kth_largest(vec![-1,-1], 1));              // -1
    println!("{}", find_kth_largest(vec![7,6,5,4,3,2,1], 7));     // 1
}

最优解讲解（通俗版 + 推理过程）

题意翻译：找第 k 大，不要求把整个数组排序完。
朴素做法：排序后取第 k 大，时间 (O(n\log n))。
关键推理：我们只关心“最大的 k 个数”，剩下的都可以丢：
- 用一个大小为 k 的 小根堆 保存“当前最大的 k 个数”。
- 堆顶是这 k 个数里最小的那个，也就是“第 k 大”的候选。
- 每来一个新数：
  - 先放进堆
  - 如果堆超过 k 个，就弹出最小的（也就是把不够大的淘汰）
处理完所有数后，堆里刚好是最大的 k 个，堆顶就是第 k 大。

类似题目（TopK 模板：小根堆保留 k 个最好）

for x in nums:
  heap.push(x)
  if heap.size > k: heap.pop() // 弹最差
return heap.peek()

347. 前 K 个高频元素

力扣原题：347. 前 K 个高频元素

Medium

数组

哈希表

分治

桶排序

计数

快速选择

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

最优解（哈希计数 + 小根堆按频次保留 k 个）

正在加载编辑器...

Rust 参考（点击展开）

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq: HashMap<i32, usize> = HashMap::new();
    for x in nums { *freq.entry(x).or_insert(0) += 1; }
    let mut heap: BinaryHeap<Reverse<(usize, i32)>> = BinaryHeap::new();
    for (num, f) in freq {
        heap.push(Reverse((f, num)));
        if heap.len() > k { heap.pop(); }
    }
    heap.into_iter().map(|Reverse((_, n))| n).collect()
}

fn main() {
    let mut r = top_k_frequent(vec![1,1,1,2,2,3], 2); r.sort(); println!("{:?}", r); // [1,2]
    println!("{:?}", top_k_frequent(vec![1], 1));                                      // [1]
    let mut r = top_k_frequent(vec![4,4,4,5,5,6], 1); r.sort(); println!("{:?}", r); // [4]
    println!("{}", top_k_frequent(vec![1,2,3,4], 2).len());                            // 2
    let mut r = top_k_frequent(vec![0,0,0,-1,-1,-2], 2); r.sort(); println!("{:?}", r); // [-1,0]
}

最优解讲解（通俗版 + 推理过程）

问题拆解：
1. 先统计每个数出现次数（哈希表）
2. 再从这些“(数,频次)”里选出频次最高的 k 个（TopK）
为什么用小根堆？：和 215 一样，“保留最好的 k 个”最稳的做法就是小根堆：
- 堆顶是当前 k 个里频次最小的（最容易被淘汰）。
- 新元素频次更大时，会把堆顶挤掉。
复杂度：统计 (O(n))，堆操作 (O(u\log k))（u 是不同元素个数），整体很高效。

类似题目（先计数再 TopK）

freq = count()
heap keep k by key=freq

295. 数据流的中位数

力扣原题：295. 数据流的中位数

Hard

设计

双指针

数据流

排序

堆（优先队列）

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

例如 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

最优解（双堆：大根堆存左半，小根堆存右半）

正在加载编辑器...

Rust 参考（点击展开）

use std::collections::BinaryHeap;
use std::cmp::Reverse;

struct MedianFinder {
    left: BinaryHeap<i32>,          // 大根堆（存较小的一半）
    right: BinaryHeap<Reverse<i32>>, // 小根堆（存较大的一半）
}

impl MedianFinder {
    fn new() -> Self { MedianFinder { left: BinaryHeap::new(), right: BinaryHeap::new() } }
    fn add_num(&mut self, num: i32) {
        if self.left.is_empty() || num <= *self.left.peek().unwrap() {
            self.left.push(num);
        } else {
            self.right.push(Reverse(num));
        }
        if self.left.len() > self.right.len() + 1 {
            let top = self.left.pop().unwrap();
            self.right.push(Reverse(top));
        } else if self.right.len() > self.left.len() {
            let Reverse(top) = self.right.pop().unwrap();
            self.left.push(top);
        }
    }
    fn find_median(&self) -> f64 {
        if self.left.len() > self.right.len() {
            *self.left.peek().unwrap() as f64
        } else {
            (*self.left.peek().unwrap() as f64 + self.right.peek().unwrap().0 as f64) / 2.0
        }
    }
}

fn main() {
    let mut mf = MedianFinder::new();
    mf.add_num(1); mf.add_num(2);
    println!("{}", mf.find_median()); // 1.5
    mf.add_num(3);
    println!("{}", mf.find_median()); // 2
}

最优解讲解（通俗版 + 推理过程）

中位数的本质：把数据分成左右两半：
- 左半都 ≤ 右半
- 两边数量尽量相等（最多差 1）
关键推理：用两个堆维护这两个半区：
- left（大根堆）：存较小的一半，堆顶是左半最大值
- right（小根堆）：存较大的一半，堆顶是右半最小值
插入一个数怎么做？
- 先把它放进合适的一边（<= left 顶就进 left，否则进 right）。
- 然后做“平衡操作”：让 left 的大小永远 >= right，且最多多 1。
中位数怎么取？
- 总数奇数：left 比 right 多 1，中位数就是 left.peek()
- 总数偶数：两边一样大，中位数是 (left.peek()+right.peek())/2

类似题目（动态维护中位数：双堆平衡）

add:
  push to left/right
  rebalance sizes
median:
  if left bigger: left.top
  else avg(left.top, right.top)

堆（题单顺序）

215. 数组中的第 K 个最大元素

347. 前 K 个高频元素

295. 数据流的中位数

On this page