堆 是一种特殊的完全二叉树，它满足以下堆序性质：
- 要么是小根堆，要么是大根堆
- 大根堆（大顶堆）：对于树中任意一个节点，其值大于或等于其左右孩子节点的值。
- 小根堆（小顶堆）：对于树中任意一个节点，其值小于或等于其左右孩子节点的值。
零、堆排序
人话：就是不断构建大（小）根堆，然后不断把根节点抽走（放到原数组的末尾）
对数组 [4, 10, 3, 5, 1] 进行升序排序。
步骤一：构建大顶堆
4 10
/ \ / \
10 3 => 5 3
/ \ / \
5 1 4 1 步骤二：排序（交换与调整）
第一趟：交换根节点(10)与最后一个节点(1)。
Array: [1, 5, 3, 4, 10] // 10已在正确位置 Heap Size: 4 (不考虑最后一个元素)对根节点(1)进行堆调整：
- 比较1, 5, 3 → 5最大，交换1和5。
- 比较1, 4 → 4最大，交换1和4。
调整后堆结构： 5 / \ 4 3 / 1 数组: [5, 4, 3, 1, 10]第二趟：交换根节点(5)与最后一个节点(1)。
Array: [1, 4, 3, 5, 10] // 5, 10已在正确位置 Heap Size: 3对根节点(1)进行堆调整：
- 比较1, 4, 3 → 4最大，交换1和4。
调整后堆结构： 4 / \ 1 3 数组: [4, 1, 3, 5, 10]第三趟：交换根节点(4)与最后一个节点(3)。
Array: [3, 1, 4, 5, 10] // 4,5,10已就位 Heap Size: 2对根节点(3)进行堆调整：
- 比较3, 1 → 无需交换。
数组: [3, 1, 4, 5, 10]第四趟：交换根节点(3)与最后一个节点(1)。
Array: [1, 3, 4, 5, 10] // 全部有序
一、数组中的第K个最大元素
中等
给定整数数组 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^5-10^4 <= nums[i] <= 10^4
思路不难想，既然是第k大，说明肯定要排序，排序完再倒着往回找即可
1.1 计数排序
排序时间复杂度为O(n)容易想到使用计数排序，由于本题限定范围-10^4 <= nums[i] <= 10^4，为避免索引为负，将每个数都加10^4
👇所以可以创建一个长度为20001的数组来存储，存储完后倒序遍历数组
for (int i = 20000; i >= 0; i--) {
k -= count[i];
if (k <= 0) return i - 10000; // k <= 0，说明已经刚好到达或者已经越过了第k大元素
}❓为什么会越过
当有重复值时，第k大可能出现在某个数值的内部
比如班级有50个人，考试成绩出来了，最高100，再下来是99，但是第二大元素不一定是99
假如有30个人考了100分，那考99分的那个人只能排到31（第31大元素）
class Solution {
/**
* 215. 数组中的第K个最大元素（计数排序）
*
* @param nums 提供的数组
* @param k 目标第k大元素
* @return 第k大元素的值
*/
public int findKthLargest(int[] nums, int k) {
int[] count = new int[20001];
for (int n : nums) count[n + 10000]++;
int ans;
int i = 20000;
while (k > 0) k -= count[i--];
return i - 9999;
}
}执行用时2ms，击败100.00%，复杂度O(N)
消耗内存69.73MB，击败15.56%，复杂度O(20001)
1.2 堆排序
class Solution {
/**
* 215. 数组中的第K个最大元素（堆排序）
*
* @param nums 提供的数组
* @param k 目标第k大元素
* @return 第k大元素的值
*/
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
// 1. 构建大顶堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--)
heapify(nums, n, i);
// 2. 逐个提取元素
for (int i = n - 1; i >= n - k + 1; i--) {
// 将当前最大值（堆顶）移到末尾
swap(nums, 0, i);
// 对剩余堆进行调整（堆大小减1）
heapify(nums, i, 0);
}
return nums[0];
}
// 交换函数
void swap(int[] nums, int a,int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
// 堆调整函数：对以节点i为根的子树进行堆调整
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大值为根
int left = 2 * i + 1; // 左孩子
int right = 2 * i + 2; // 右孩子
// 如果左孩子存在且大于根
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右孩子存在且大于当前最大值
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大值不是根
if (largest != i) {
swap(arr, i, largest);
// 递归调整被破坏的子堆
heapify(arr, n, largest);
}
}
}执行用时28ms，击败59.91%，复杂度O(N * logN)
消耗内存68.82MB，击败41.97%，复杂度O(logN)
二、前 K 个高频元素
中等
给你一个整数数组 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^5-10^4 <= nums[i] <= 10^4k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
2.1 堆排
与上一道题非常相似，一个是数值第k大，一个是频率第k大
那么可以进行一个转换：把频率变为数值
即用频率去确定数值的大小，在这种反常规思维下，1也可以比2大
在倒序查找的过程一直把沿途对应的数字放进答案数组即可
class Solution {
Map<Integer, Integer> map = new HashMap<>(); // 统计频率
/**
* 347. 前 K 个高频元素（堆排序）
*
* @param nums 提供的数组
* @param k 频率前k大元素
* @return 频率前k大元素的值
*/
public int[] topKFrequent(int[] nums, int k) {
for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
int[] arr = new int[map.size()];
int i = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) arr[i++] = entry.getKey();
int length = arr.length;
for (int j = length / 2 - 1; j >= 0; j--) heapify(arr, j, length);
int[] res = new int[k];
for (int j = 0; j < k; j++) {
res[j] = arr[0];
swap(arr, 0, length - j - 1);
heapify(arr, 0, length - j - 1);
}
return res;
}
void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public void heapify(int[] arr, int i, int length) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < length && map.get(arr[l]) > map.get(arr[largest])) largest = l;
if (r < length && map.get(arr[r]) > map.get(arr[largest])) largest = r;
if (largest != i) {
swap(arr, largest, i);
heapify(arr, largest, length);
}
}
}执行用时13ms，击败78.77%，复杂度O(N * LogN)
消耗内存46.63MB，击败89.67%，复杂度O(N)
2.2 优先队列
优先队列的底层就是堆
class Solution {
/**
* 347. 前 K 个高频元素（优先队列）
*
* @param nums 提供的数组
* @param k 频率前k大元素
* @return 频率前k大元素的值
*/
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(
(a, b) -> b.getValue() - a.getValue()
); // 大根堆
for (Map.Entry<Integer, Integer> entry : map.entrySet()) queue.add(entry);
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = queue.poll().getKey();
return res;
}
}三、数据流的中位数
困难
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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^5 <= num <= 10^5- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 10^4次调用addNum和findMedian
3.1 优先队列
在存储数据时候，可以分成两部分存储
- 一半存储小于等于中位数的数据
- 一半存储大于中位数的数据
为了取出方便（只取堆顶就能取出中位数或附近的两个数），可以定义：
sml：存储小于等于中位数的数据，为大根堆big：存储另一半数据，为小根堆
取出中位数时，只需要判断当前数据总个数size：
- 如果是奇数，直接返回
sml（比中位数小的那部分数据）的堆顶 - 如果是偶数，返回两个堆顶的平均值
由此可见，在插入时
- 如果
size为偶数，插入sml- 如果
big部分有数据且堆顶比新插入的num还要小 - 弹出
big顶插入sml，big顶插入新的num - 示例：
sml = [-1], big = [1], num = 6 - 结果：
sml = [-1, 1], big = [6]
- 如果
- 如果
size为奇数，插入big- 与上边同理
class MedianFinder {
private PriorityQueue<Integer> sml; // 存储<=中位数
private PriorityQueue<Integer> big; // 存储>中位数
private int size;
/**
* 295. 数据流的中位数（优先队列）
*/
public MedianFinder() {
sml = new PriorityQueue<Integer>((a, b) -> (b - a)); // 大根堆
big = new PriorityQueue<Integer>((a, b) -> (a - b)); // 小根堆
size = 0;
}
public void addNum(int num) {
if (size % 2 == 0) { // 插入比中位数小的那部分
// 如果插入的数比小顶堆的堆顶还大
if (big.size() > 0 && num > big.peek()) {
sml.add(big.poll()); // 弹出小顶堆的元素，加入大顶堆
big.add(num); // 小顶堆加入新插入的 num
} else sml.add(num);
} else { // 插入比中位数大的那部分
if (num < sml.peek()) {
big.add(sml.poll());
sml.add(num);
} else big.add(num);
}
size++;
}
public double findMedian() { // 题目中保证调用此方法时一定有元素
if (size % 2 == 1) return (double)sml.peek();
return (double)(sml.peek() + big.peek()) / 2.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/执行用时115ms，击败91.49%
消耗内存109.50MB，击败49.31%
Thanks for reading!
力扣hot100-《堆》章节题解
周六 1月 17 2026 堆
2722 字 · 16 分钟