Java中类PriorityQueue就是堆的实现，下面是使用它的使用方法：
// 自定义比较器
Queue<Integer> queue = new PriorityQueue<>(
new Comparator(){
@Override
public int compare(Object o1, Object o2){
// 可在这使用局部变量
}
}
);
// 更简洁的写法
Queue<Integer> queue = new PriorityQueue<>((n1, n2) -> n1 - n2);
// 删除堆顶元素，时间复杂度为O(log k)，k为堆元素的个数，
queue.remove();
// 将一个元素插入堆中，时间复杂度为O(log k)
queue.add(0);
// 获取堆顶元素
queue.peek();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
堆常见问题？
- 自己实现一个堆的数据结构，可以插入删除，堆排序
- 求Top k问题（堆、快选）
- 求中位数
- k路归并
# 经典例题
# 347. 前 K 个高频元素 (opens new window)
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
1
2
2
示例 2:
输入: nums = [1], k = 1
输出: [1]
1
2
2
使用map记录每个元素的频率，维护一个按照频率排序小顶堆，遍历map，不断将元素加入堆中，当堆中元素大于k的时候，移除一次堆顶元素，遍历之后，堆中k个元素就是出现频率最高的。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
Queue<Integer> queue = new PriorityQueue<>(
new Comparator(){
@Override
public int compare(Object o1, Object o2){
// 可在这使用局部变量map
return map.get((int)o1) - map.get((int)o2);
}
}
);
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
}
for(int key : map.keySet()){
queue.add(key);
if(queue.size() > k){
queue.remove();
}
}
int[] ans = new int[queue.size()];
for(int i = 0; i < ans.length; i++){
ans[i] = queue.remove();
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28