InTheBloodHorse

数据结构与算法(1)-二叉堆

字数统计: 1.5k阅读时长: 6 min
2018/09/14 Share

二叉堆

1:什么是二叉堆?
ans:二叉堆的本质是完全二叉树,可以分为最大堆和最小堆。
二叉堆可以实现优先队列,插入和删除的复杂度都为O(logN)
用堆实现的优先队列 数据结构与算法(4) 堆(优先队列)

最大堆

最大堆任何父节点的值,都大于等于它的左右子节点的值。

最小堆

最小堆任何父节点的值,都小于等于它的左右子节点的值。

二叉堆的根节点叫做堆顶,毫无疑问,就是二叉树的最大值或者最小值

插入节点(复杂度 log(N))

假设我们已经有了一个最小堆,如图TIM截图20180914102452.jpg
1.我们插入一个节点为 0(绿色),我们需要把插入的节点追加到树的最后一个节点 如图TIM截图20180914102851.jpg
2.将插入的节点与父节点比较,假如值小于父节点,使父节点下沉。得到TIM截图20180914102914.jpg
3.重复上述的操作,结果为
TIM截图20180914102934.jpgTIM截图20180914102950.jpg

删除节点(复杂度 log(N))

假设我们删除堆顶节点0,与插入相反,我们删除我们要删除的节点,把最后一个节点拿过来,补回去,这样才可以是一个完全二叉树。TIM截图20180914103802.jpg
1.父节点和左右子节点的最小值比较,假如父节点值大于最小值,交换两个节点,以此类推。
TIM截图20180914103840.jpgTIM截图20180914103906.jpgTIM截图20180914103932.jpgTIM截图20180914103949.jpg

构建最小堆(复杂度 Nlog(N))

把一棵无序完全二叉树构建成最小堆,出发点,最后一个非叶子节点开始下沉。
TIM截图20180914100545.jpg
1.在这里就是 2 节点 ,2 和 min(5,3)比较,因为 2 < 3 所以没必要交换了
2.接下来是 9号节点,9 和 min(8,4)比较,因为 9 > 4 所有要交换,得到TIM截图20180914100833.jpg
3.接下来是 7号节点,7 和 min(2,1)比较,因为 7 > 1 所有要交换,得到TIM截图20180914100930.jpg
4.接下来是 6号节点,6 和 min(1,4)比较,因为 6 > 1 所有要交换,得到TIM截图20180914101941.jpg
5.还没结束,因为 6号节点下沉了,所以我们还要判断6号能否继续下沉,6 和 min(2,7)比较,因为 6 > 2 所有要交换,得到TIM截图20180914101841.jpg
6.接下来还是是 6号节点,6 和 min(5,3)比较,因为 6 > 3 所有要交换,得到TIM截图20180914102123.jpg
好了,到底为止,我们就把无序的完全二叉树构建成了最小堆。
总结:从最后一个非叶子节点开始下沉,符合条件(当前节点 小于 min(left,right))下沉。
顺带提一下,这里的树是用顺序存储的,所以 对于 任意一个父节点位置为n,它的子节点位置为 n × 2+1,n × 2+2
代码:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
using namespace std;
int maxn = 1e9;
// 存放节点
vector<int>v;
int number = 10; // 初始化的树的节点个数
bool is_small_heap = false; // 判断当前是不是 最小堆
void get_random_tree(){
srand((int)time(NULL));
for(int i=0;i<number;i++){
v.push_back(rand()%20); //随机生成数字并插入
}
cout << "生成的完全二叉树为: ";
for(int i=0;i<v.size();i++) cout << " " << v[i];
cout << endl;
}
// 这个函数是 交换 节点的
void swap_node(int i,int node_count,int leaf_count){
int now_node = i;
while(1){
if(now_node>=node_count-leaf_count) break;
int chl_left = 2*now_node + 1;
int chl_right = chl_left + 1;
int val_left = v[chl_left];
int val_right;
if(chl_right>=v.size()) val_right = maxn; // 可能会出现只有左节点,没有右节点
else val_right=v[chl_right];
if(v[now_node] > min(val_right,val_left)){
now_node = chl_left;
if(val_right < val_left) now_node++;
}else break;
}
swap(v[i],v[now_node]);
// 再次调用,因为 还要判断交换后的节点 能否继续下沉
// 具体看倒数第三张图
if (i!=now_node) swap_node(now_node,node_count,leaf_count);
}
void generate_small_heap(){
int node_count = v.size(); //节点个数
int leaf_count = (node_count+1)/2 ; // 叶子节点
for(int i=node_count-leaf_count-1;i>=0;i--){
// 从最后一个非叶子节点开始遍历
swap_node(i,node_count,leaf_count);
}
is_small_heap = true;
cout << "生成的最小堆为:" << endl;
for(int i=0;i<v.size();i++){
cout << v[i] << " " ;
}
cout << endl;
}

// 插入节点,自下而上寻找,交换
void insert_node(int new_node){
v.push_back(new_node);
int father_node; //父亲节点的位置
int now_index=v.size()-1; //目前插入的节点所在的位置
while(1){
father_node = (now_index-1)/2;
if(new_node < v[father_node]){
swap(v[now_index],v[father_node]);
now_index= father_node;
}else break;
}
cout << "生成的最小堆为:" << endl;
for(int i=0;i<v.size();i++){
cout << v[i] << " " ;
}
cout << endl;
}

void delete_node(int node){
swap(v[node],v[v.size()-1]); // 最后一个节点和需要删除的节点换位
v.pop_back(); // 移除最后一个节点
int now_node = node;
while(1){
if(now_node >= v.size() - ( v.size()+1)/2 ) break; //是叶子节点就说明结束了
int left = now_node * 2 + 1;
int right = now_node * 2 + 2;
int val_left = v[left];
int val_right;
if(right >= v.size()) val_right=maxn;
else val_right = v[right];
if(v[now_node] > min(val_left,val_right)){
int change = left;
if(val_left > val_right) change=left+1;
swap(v[now_node],v[change]);
now_node = change;
}else break;
}
cout << "生成的最小堆为:" << endl;
for(int i=0;i<v.size();i++){
cout << v[i] << " " ;
}
cout << endl;
}
int main()
{
get_random_tree();
cout << "请选择操作:" << endl;
cout << "1:生成最小堆" << endl;
cout << "2:插入节点" << endl;
cout << "3:删除节点" << endl;
int n;
while(1){
cin >> n;
switch(n){
case 1:{
generate_small_heap();
break;
};
case 2:{
if(is_small_heap == false){
cout << "先生成最小堆" << endl;
break;
}
int new_node;
cout << "输入添加的节点" << endl;
cin >> new_node;
insert_node(new_node);
break;
};
case 3:{
if(is_small_heap == false){
cout << "先生成最小堆" << endl;
break;
}
int node;
cout << "输入删除的节点坐标[0 , number-1]" << endl;
cin >> node;
delete_node(node);
break;
}
}
}
}

CATALOG
  1. 1. 二叉堆
    1. 1.1. 最大堆
    2. 1.2. 最小堆
      1. 1.2.1. 插入节点(复杂度 log(N))
      2. 1.2.2. 删除节点(复杂度 log(N))
      3. 1.2.3. 构建最小堆(复杂度 Nlog(N))