堆以及堆排序详解
标签：return 就是 理解 scan main color 下标 namespace 说明
记录一下自己理解的堆和堆排序吧。
堆是一种类似于完全二叉树的树形结构，对于二叉树中所有非叶子节点，如果根节点的值严格大于其两个儿子的值，则称为
大顶堆，反之称为小顶堆。
堆排序的一般步骤：
首先利用已有的数据构造一个堆，大顶堆增序，小顶堆降序。
将堆顶的元素与堆末元素交换，接着重新调整除去堆末元素的二叉树为一个堆(并将堆末变为倒数第二个元素)，直到堆
末等于堆顶。
如何把无序数组建堆。
首先说明一个下沉调整法。
言下之意就是对于一个节点，如果其存在值大于此节点的儿子，就交换他们，并对这个儿子节点再进行调整。
对于一个长度为n的无序数组，如果下标从1 ~ n，那么必定仅有n / 2个结点有子节点。我们从第n / 2个结点开始将前面
所有节点进行下沉调整，即得到一个堆。
1 #include 2 using namespace std;
3
4 const int maxn = 100 + 5;
5 int val[maxn];
6
7 void swap(int a, int b) {
8 int t = val[a];
9 val[a] = val[b];
10 val[b] = t;
11 }
12
13 void sink(int n, int i) {
14 int max = i;
15 int l = i 1, r = i 1 | 1;
16 if(l val[max]) max = l;
17 if(r val[max]) max = r;
18 if(max != i) {
19 swap(max, i);
20 sink(n, max);
21 }
22 }
23
24 void heap_sort(int n) {
25 for(int i = n / 2; i >= 1; i --) {
26 sink(n, i);
27 }
28 for(int i = n; i > 1; i --) {
29 swap(1, i);
30 //printf("%d %d\n", val[1], val[i]);
31 sink(i - 1, 1);
32 }
33 }
34
35 int main() {
36 int n;
37 scanf("%d", &n);
38 for(int i = 1; i ) {
39 scanf("%d", &val[i]);
40 }
41 heap_sort(n);
42 for(int i = 1; i ) {
43 printf("%d ", val[i]);
44 }
45 puts("");
46 return 0;
47 }
堆以及堆排序详解
标签：return 就是 理解 scan main color 下标 namespace 说明
原文地址：https://www.cnblogs.com/bianjunting/p/13178956.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
堆以及堆排序详解
文章链接：http://soscw.com/index.php/essay/83979.html
评论