堆排序

发表于 | 分类于

堆是一种特殊的完全二叉树（除了最后一层节点之外，其它层的节点必须是最大值），然后最后一层的节点必须集中在最左侧。

创建堆

把 n 个元素建立成一个堆，首先我可以将这 n 个节点以自顶向下，从左到右的方式从 1 到 n 编码。这样就可以把这 n 个节点转换成为一棵完全二叉树，紧接着从最后一个非叶节点（节点编号为 n/2）开始到根节点(节点编号为1)逐个扫描所有节点，根据需要将当前节点向下调整，直到以当前节点为根节点的子树符合堆的特性：

1
2
3
4
// 从最后一个非叶结点到第1个结点依次进行向下调整
for(i=n/2;i>=1;i--){
	siftdown(i);
}

最大堆

所有父节点都比子节点要大：

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
#include <stdio.h> 

int h[101]; // 用来存放堆的数组
int n; // 用来存储堆中元素的个数，也就是堆的大小

// 交换函数，用来交换堆中的两个元素的值
void swap(int x,int y){
	int t;
	t=h[x];
	h[x]=h[y];
	h[y]=t;
}

// 向上调整
void shiftUp(int k) {
	while(k > 1 && h[k/2] < h[k]){
		swap(k/2,k);
		k /= 2;
	}
}

// 插入元素,item为插入值，count为当堆元素的数量
void insert(int item, int count) {
	h[count + 1] = item
	count++
	shiftUp(count)
}

// 向下调整函数
void siftdown(int i) { // 传入一个需要向下调整的节点编号i,这里传入1，即从堆的顶点开始向下调整
	int t,flag=0;// flag用来标记是否需要继续向下调整
	while(i*2<=n && flag==0){
		// 首先判断它和左儿子的关系(至少有左儿子)，并用t记录值较大的结点编号
		if(h[i] < h[i*2]){
			t=i*2;
		}else{
			t=i;
		}
		// 如果它有右儿子，再对右儿子进行比较
		if(i*2+1 <= n){
			// 如果右儿子的值更大，更新较大的节点编号
			if(h[t]<h[i*2+1]){
				t=i*2+1;
			}
		}
		// 如果发现最大的结点编号不是自己，说明结点中有比父结点更大的数
		if(t!=i){
			swap(t,i); // 交换它们，注意swap函数需要自己来写
			i=t; // 更新i为刚才与它交换的儿子的结点编号，便于接下来继续向下调整
		}else{
			flag=1; // 否则说明当前的父结点已经比两个子结点都要小了，不需要再进行向下调整了
		}
	}
}

// 建立堆函数
void creat(){
	int i;
	// 从最后一个非叶结点到第1个结点依次进行向下调整
	for(i=n/2;i>=1;i--){
		siftdown(i);
	}
}

// 堆排序
void heapsort(){
	while (n>1){
		swap(1,n);
		n--;
		siftdown(1);
	}
}

int main() 
{
	int i,num;
	// 读入需要配许的数字的个数
	scanf("%d",&num);
	
	for(i=1;i<=num;i++){
		scanf("%d",&h[i]);
	}
	n=num;

	// 建堆
	creat();

	// 堆排序
	heapsort();

	// 输出
	for(i=1;i<=num;i++){
		printf("%d ",h[i]);
	}

	getchar();
	getchar(); 
	return 0; 
}

// 测试用例:
// 14
// 99 5 36 7 22 17 46 12 2 19 25 28 1 92

最小堆

所有父节点都比子节点要小：

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
#include <stdio.h> 

int h[101]; // 用来存放堆的数组
int n; // 用来存储堆中元素的个数，也就是堆的大小

// 交换函数，用来交换堆中的两个元素的值
void swap(int x,int y){
	int t;
	t=h[x];
	h[x]=h[y];
	h[y]=t;
}

// 向下调整函数
void siftdown(int i) { // 传入一个需要向下调整的节点编号i,这里传入1，即从堆的顶点开始向下调整
	int t,flag=0;// flag用来标记是否需要继续向下调整
	while(i*2<=n && flag==0){
		// 首先判断它和左儿子的关系，并用t记录值较小的结点编号
		if(h[i] > h[i*2]){
			t=i*2;
		}else{
			t=i;
		}
		// 如果它有右儿子，再对右儿子进行比较
		if(i*2+1 <=n){
			// 如果右儿子的值更小，更新较小的节点编号
			if(h[t]>h[i*2+1]){
				t=i*2+1;
			}
		}
		// 如果发现最小的结点编号不是自己，说明结点中有比父结点更小的数
		if(t!=i){
			swap(t,i); // 交换它们，注意swap函数需要自己来写
			i=t; // 更新i为刚才与它交换的儿子的结点编号，便于接下来继续向下调整
		}else{
			flag=1; // 否则说明当前的父结点已经比两个子结点都要小了，不需要再进行向下调整了
		}
	}
}

// 建立堆函数
void creat(){
	int i;
	// 从最后一个非叶结点到第1个结点依次进行向下调整
	for(i=n/2;i>=1;i--){
		siftdown(i);
	}
}

// 删除最小的元素堆顶元素，删除堆里面的最后一个元素放到第一个进行向下调整操作
int deletemin(){
	int t;
	t=h[1]; // 用一个临时变量记录堆顶的值
	h[1]=h[n]; // 将堆的最后一个点赋值到堆顶
	n--; // 堆的元素减少1
	siftdown(1); // 向下调整
	return t; // 返回之前记录的堆的顶点的最小值
}

int main() 
{
	int i,num;
	// 读入需要配许的数字的个数
	scanf("%d",&num);
	
	for(i=1;i<=num;i++){
		scanf("%d",&h[i]);
	}
	n=num;

	// 建堆
	creat();

	// 删除顶部元素，连续删除n次，其实也就是从大到小把数输出来
	for(i=1;i<=num;i++){
		printf("%d ",deletemin());
	}

	getchar();
	getchar(); 
	return 0; 
}

// 测试用例:
// 14
// 99 5 36 7 22 17 46 12 2 19 25 28 1 92