0%

5.25创新班总结

今天,我们主要是认识了一种新的数据结构,堆。

定义:堆,顾名思义,就是把东西堆在一起,类似于一座金字塔。其实,堆也是一棵树,不过是一颗完全二叉树。也就是说,对于一个根节点来说,它只有三种状态:①没有孩子②只有左孩子③即有左孩子,又有右孩子。并不存在,只有右孩子的状态存在。

性质:对于一个堆来说,由于它是一个完全二叉树,因此,我们自上而下把它进行编号,如图:

他不见了。

那么,对于一个根节点的编号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) //维护堆
{
//fout << k << ' ' << x << ' ' << len << endl;

while ((k<<1<=len) && ((x>a[k<<1]) || (x>a[k<<1+1])))
{
//fout << "**" << k << endl;

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;
}
Thank you so much.