堆
🟧概述
🔻含义： 堆是通过数组化二叉树 同时通过构建堆和重建堆 来实现获取最大值和最小值的数据结构
🔻试用场景： 查找最大值和最小值、排序、频率、topK问题
🔻时间复杂度： O(nlogN)
🔻空间复杂度： O(1)
🔻注意事项：
🔸是使用大根堆还是小根堆
🟧模板
📌优先队列
1
2
3
4
5
6
7
8
9
class Solution {
public int heap(int[] nums) {
//默认小根堆
PriorityQueue<Integer> minHeap =new PriorityQueue<>((a,b)->(int)(a-b));
//大根堆
PriorityQueue<Integer> maxHeap =new PriorityQueue<>((a,b)->(int)(b-a));
}
}
📌原生写法
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
//堆排序
public int[] sortArray(int[] nums) {
heapSort(nums);
return nums;
}
public void heapSort(int[] nums) {
int len = nums.length-1;
buildHeap(nums,len);
for(int i=len;i>=1;--i){
swap(nums,i,0);
--len;
reBuildHeap(nums,len,0);
}
}
public void buildHeap(int[] nums,int len) {
for(int i=len/2;i>=0;--i){
reBuildHeap(nums,len,i);
}
}
public void reBuildHeap(int[] nums,int len,int i) {
for(;((i<<1)+1)<=len;){
int l=(i<<1)+1;
int r=(i<<1)+2;
int big=0;
if(l<=len&&nums[l]>=nums[i]){
big = l;
}else{
big = i;
}
if(r<=len&&nums[r]>=nums[big]){
big = r;
}
if(i!=big){
swap(nums,i,big);
i=big;
}else{
break;
}
}
}
void swap(int[]nums,int l,int r){
int t = nums[l];
nums[l]=nums[r];
nums[r]=t;
}
}
🟧总结
🔻总结1:堆的各项复杂度指标
🔸时间复杂度:O(nlogN)
🔸空间复杂度:O(1)
🔻总结2:堆使用场景
🔸排序、topK等
🟧思考
🔻思考1:堆的为何使用数组化二叉树存储数据?
🔸
🟧泛化
🔻泛化1:从堆使用数组化二叉树存储数据能得到什么启发?
🔸