大顶堆与小顶堆
根结点大 大顶堆
根节点小 小顶堆
堆每次pop 都是根元素
所有小顶堆最终保留大元素
大顶堆最终保留小元素
优先级队列
其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
leetcode 347
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
| class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.get(nums[i])==null?1:map.get(nums[i])+1);
}
PriorityQueue<int[]> pq=new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
for(Map.Entry<Integer,Integer> m:map.entrySet()){
pq.add(new int[]{
m.getKey(),m.getValue()});
if(pq.size()>k){
pq.poll();
}
}
int []res=new int[k];
for(int i=0;i<k;i++){
res[i]=pq.poll()[0];
}
return res;
}
}
|
也可以利用entry
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
| class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.get(nums[i])==null?1:map.get(nums[i])+1);
}
PriorityQueue<Map.Entry<Integer,Integer> > pq=new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
for(Map.Entry<Integer,Integer> m:map.entrySet()){
pq.add(m);
if(pq.size()>k){
pq.poll();
}
}
int []res=new int[k];
for(int i=0;i<k;i++){
res[i]=pq.poll().getKey();
}
return res;
}
}
|
