数据结构之二叉堆学习笔记

发表于 | 更新于 | 评论数： | 阅读次数：

这真的是一种数据结构，尽管名字有点。。。。

前言

昨天（2019/1/19）$Payphone-X​$问我堆应该如何实现，当时讲的太仓促，言语特别混乱，于是就有了这篇文章。

二叉堆是什么

二叉堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。 ——百度百科

书面上的定义不太好理解，那我们讲得通俗一点。

实际上二叉堆是一棵完全二叉树，但它比完全二叉树多了以下两个性质：

1、堆中的每一个节点总是不大于（或不小于）其父节点。

2、无论如何调整堆，它总是一棵完全二叉树（这不是废话吗）。

那么，根据第一条性质，二叉堆就可以分为大根堆和小根堆两种。

我们将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

5jMwhB.png

如图，这就是大根堆和小根堆的一个实例。

这是按根节点的大小来分，如果按操作种类来分，那么常见的堆有二叉堆、斐波那契堆等。

如何存储

堆是线性数据结构，相当于一维数组，有唯一后继。

所以在代码实现时，我们用一个一维数组Heap[]来存储堆。

学过完全二叉树的同学们都知道，完全二叉树有这样一个性质，即一个非叶节点i的左儿子的编号为2i，其右儿子的编号为2i+1。

那么既然堆是一棵完全二叉树，那么也应该满足这个性质。

所以当一个有$n$个元素的序列${Heap_1,Heap_2,Heap_3,\dots,Heap_n}$满足：

$Heap_i \leq Heap_{2i} \& Heap_i \leq Heap_{2i+1}​$,（小根堆）

或者：
$Heap_i \geq Heap_{2i} \& Heap_i \geq Heap_{2i+1}​$（大根堆）

时，这个序列称为一个堆。

那么，我们就可以得出，堆顶元素必为这个序列中最大或最小的元素。

操作

一个堆支持以下四个操作。

1、插入一个节点；

2、删除堆顶元素；

3、获取堆顶元素；

4、堆排序。

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

时间复杂度

堆的插入和删除的时间复杂度均为$O(1)-O(\log n)$。

获取堆顶元素为$O(1)$。

堆排序为$O(n \log n)$，和快排的时间复杂度一样，但空间复杂度为$O(2n)$，比快排高了一倍。

操作实现

在插入和删除两个操作中，还嵌套着两个小操作。

1、$shiftUp​$上浮。

2、$shiftDown​$下沉。

一、上浮

当我们插入一个节点时，（我们现在以小根堆为例）。

根据小根堆的性质，（每一个节点总是不小于其父节点）。

那么首先我们要和它的父节点比较，如果这个节点小于它的父节点，那么交换。

然后继续比较，交换后的节点和它现在的父节点继续比较，如果还小于，那么继续交换。

直到这个节点要比它的父节点大时，或这个节点成为根节点时，停止比较。

这就是上浮操作。

来看这个图：
5jOmxQ.png

假如我们刚刚插入了一个节点，其点权为2。

那么就要开始上浮操作了：

第一步，交换节点7（点权为2）和它的父亲节点3（点权为4）。

5jOVm2.png

第二步，交换节点3（点权为2）和节点1（点权为7）

5jOYha.png

最后一步，交换节点3（点权为7）和节点7（点权为4）

5jO0kz.png

至此，这棵完全二叉树就满足堆的性质了。

二、下沉

下沉操作是用来删除堆顶元素的。

当我们删除掉堆顶元素时，把叶子节点中的最后一个拿到根节点上。

当这个节点的左儿子不大于当前堆的大小时，即操作编号不越界时，

找出这个节点的左儿子和右儿子中小的那一个。

再用找出来的这一个和它们的父亲相比较，如果不满足性质，那么交换。

操作位置移至当前节点的左儿子上。

这就是下沉操作。

代码实现

大根堆

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
/* Headers */
#include<cstdio>
#include<cstring> 
#include<cmath>
#include<iostream>
#include<cctype>
using namespace std;
/* definitions */
const int MAXN = 1e5+7;
int Heap[MAXN],Size,n;
string op;
/* functions */
inline int LeftChild(int x){
	return (x<<1);
}
inline int RightChild(int x){
	return (x<<1)+1;
}
inline void shiftUp(int point){//上浮操作
	while(point>1&&Heap[point/2]<Heap[point]){
		swap(Heap[point/2],Heap[point]);
		point/=2;
	}
}
inline void shiftDown(int point){//下沉操作
	int Temp;
	while(LeftChild(point)<=Size){
	if(RightChild(point)<=Size&&Heap[RightChild(point)]>Heap[LeftChild(point)])
			Temp=RightChild(point);
		else Temp=LeftChild(point);
		if(Heap[Temp]>Heap[point]){
			swap(Heap[Temp],Heap[point]);
            point=Temp;
		}
		else break;
	}
}
inline void push(int x){//插入操作
	Heap[++Size]=x;
	shiftUp(Size);
}
inline void pop(){//弹出操作
	Heap[1]=Heap[Size--];
	shiftDown(1);
}
inline int top(){//获取堆顶元素
	return Heap[1];
}
int main(int argc,char *argv[]){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op=="push"){
			int x;
			scanf("%d",&x);
			push(x);
		}
		if(op=="pop"){
			pop();
		}
		if(op=="top"){
			if(!Size){
				printf("There isn't any elements\n");//当前堆为一个空堆
				continue;
			}
			else{
				int x=top();
				printf("%d\n",x);
			}
		}
	}
	return 0;
}

小根堆

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
/* Headers */
#include<cstdio>
#include<cstring> 
#include<cmath>
#include<iostream>
#include<cctype>
using namespace std;
/* definitions */
const int MAXN = 1e5+7;
int Heap[MAXN],Size,n;
string op;
/* functions */
inline int LeftChild(int x){
	return (x<<1);
}
inline int RightChild(int x){
	return (x<<1)+1;
}
inline void shiftUp(int point){
	while(point>1&&Heap[point/2]>Heap[point]){
		swap(Heap[point/2],Heap[point]);
		point/=2;
	}
}
inline void shiftDown(int point){
	int Temp;
	while(LeftChild(point)<=Size){
		if(RightChild(point)<=Size&&Heap[RightChild(point)]<Heap[LeftChild(point)]){
			Temp=RightChild(point);
		}
		else Temp=LeftChild(point);
		if(Heap[Temp]<Heap[point]){
			swap(Heap[Temp],Heap[point]);
            point=Temp;
		}
		else break;
	}
}
inline void push(int x){
	Heap[++Size]=x;
	shiftUp(Size);
}
inline void pop(){
	Heap[1]=Heap[Size--];
	shiftDown(1);
}
inline int top(){
	return Heap[1];
}
int main(int argc,char *argv[]){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op=="push"){
			int x;
			scanf("%d",&x);
			push(x);
		}
		if(op=="pop"){
			pop();
		}
		if(op=="top"){
			if(!Size){
				printf("There isn't any elements\n");
				continue;
			}
			else{
				int x=top();
				printf("%d\n",x);
			}
		}
	}
	return 0;
}

STL实现

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
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std; 
/* definitions */
const int MAXN = 1e5+7;
int n,Size;
vector<int>Heap;
string op;
inline bool cmp(int x,int y){
	return x>y;
}
int main(int argc,char *argv[]){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op=="push"){
			int x;
            scanf("%d",&x);
			Heap.push_back(x);
			Size++;
			if(Size==1)make_heap(Heap.begin(),Heap.end(),cmp);
			else{
				push_heap(Heap.begin(),Heap.end(),cmp);
			}
		}
		if(op=="pop"){
			pop_heap(Heap.begin(),Heap.end(),cmp);
			Heap.pop_back();
		}
		if(op=="top"){
			if(Size){
				int x;
				x=Heap[0];
				printf("%d\n",x);
			}
			else{
				printf("There isn't any elements\n");
				continue;
			}
		}
	}
	return 0;
}

堆排序

本质上就是把一个数组里的所有数插进堆里，然后每一次取出堆顶，就已经排好序列了。

正序：小根堆，逆序：大根堆。

时间复杂度:$O(n\log n)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void Heap_Sort(){
	int N,array[MAXN];
	priority_queue<int, vector<int>, greater<int> >Q;//定义一个小根堆
	scanf("%d",&n);
	for(int i=0;i<=n-1;i++){
		scanf("%d",&array[i]);
		Q.push(array[i]);
	}
	for(int i=0;i<=n-1;i++){
		printf("%d ",Q.top());
		Q.pop();
	}
}

警告：

我觉得有一句话说得很好：STL只能是锦上添花，而不能是雪中送炭！

THE END