今天，我们主要是认识了一种新的数据结构，堆。
定义：堆，顾名思义，就是把东西堆在一起，类似于一座金字塔。其实，堆也是一棵树，不过是一颗完全二叉树。也就是说，对于一个根节点来说，它只有三种状态：①没有孩子②只有左孩子③即有左孩子，又有右孩子。并不存在，只有右孩子的状态存在。
性质：对于一个堆来说，由于它是一个完全二叉树，因此，我们自上而下把它进行编号，如图：
他不见了。
那么，对于一个根节点的编号k来说，它的左孩子为k2，右孩子为k2+1，而它的父节点就是[k/2]。这也是完全二叉树的性质。
建堆：对于一个堆，由于我们知道了上述性质，所以，我们就可以用一个数组来储存这一个堆。我们可以将平常那样正常读入，通过[k2]、[k2+1]和[k/2]来找到左孩子、右孩子和根节点。
建最小堆（或最大堆）：首先我们要明确一点，那就是，对于一个堆来说，根节点总比它的左孩子，右孩子小（大）。
他不见了。
那么，这一点我们可以在读入完成。
① 我们每读入一个数时，无论大小，先把它放在堆末（即数组的最后面）。
② 我们跟它的父节点[k/2]进行比较，如果这个数比它的父节点小（大），则父节点，与当前节点交换。
③ 这样，我们就把问题变成了它的根节点。
④ 只要当前节点大于（小于）父节点，或者当前节点就是堆顶，那么，任务完成。
维护最小堆（最大堆）：如果我把堆顶的那个数据拿走，但我们还要维护好最小堆（最大堆），那怎么办呢？
① 我们那就把堆末的那个数据提上来，补掉那个窟窿。现在，我们的任务是达这个补上来的数据安排到合适的位置了。
② 首先，我们先盘判断它的左右孩子，选择数据更小的那个孩子。因为如果选择数据更大的，那么结果就不是最优了。因为，把大的孩子那个交换上来后，必然会大于小的那个孩子，结果不优了。
③ 那么，我们交换根节点和选择的那个孩子的数据。
④ 现在，我们的任务就变成对那个选择的孩子再次进行上述步骤了。如果这个节点小于它的左右孩子，或没有孩子了，任务完成。
堆排序：对于一个最小堆（最大堆），我们发现堆顶的就是最小的（最大的）数据，那么，我们一一取掉堆顶，并维护最小堆（最大堆），就可以达到一种排序的效果。我们发现，很多地方都是[2][2+1][/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
| #include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("Heap.in");
ofstream fout("Heap.out");
const int maxn=20+5;
int a[1<<maxn],n,b[1<<maxn];
void Heap_up(int k,int x)
{
while ((k>1) && (x<a[k>>1]))
{
swap(a[k],a[k>>1]);
k=k>>1;
}
a[k]=x;
}
void Heap_down(int k, int x, int len)
{
while ((k<<1<=len) && ((x>a[k<<1]) || (x>a[k<<1+1])))
{
int s1=k<<1,s2=k<<1 | 1,s;
if (s2>len) s=s1;
else
{
if (a[s1]<a[s2]) s=s1;else s=s2;
}
swap(a[s],a[k]);
k=s;
}
}
void Heap_sort(int l, int r)
{
int j=r,m=0;
for (int i=l; i<=r; ++i)
{
b[++m]=a[1];
a[1]=a[j];
j--;
Heap_down(1,a[1],j);
}
memcpy(a,b,sizeof(a));
}
void init()
{
fin >> n;
for (int i=1; i<=n; ++i)
{
int t;
fin >> t;
Heap_up(i,t);
}
}
void write()
{
for (int i=1; i<=n; ++i) fout << a[i] << ' ';
fout << endl;
}
int main()
{
init();
Heap_sort(1,n);
write();
return 0;
}
|
