发表更新算法设计

POJ 1080 Human Gene Functions（动态规划）

一开始用的DFS，无限TLE，贴丑代码

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
//version 1 TLE
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX_INT 2147483647
#define MAXN 105

using namespace std;

int Map[5][5] = {
				{0,-3,-4,-2,-1},
				{-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5},
				};
int seq1[MAXN],seq2[MAXN],Max,n1,n2;

int ref(char c)
{
	switch (c)
	{
		case 'A':
			return 1;
		case 'C':
			return 2;
		case 'G':
			return 3;
		case 'T':
			return 4;
	}
}

void dfs(int id1,int id2,int sum)
{
	if(id2 <= n2 + 1)
	{
		if(id2 == n2 + 1)
		{
			for(int i = id1;i <= n1;i ++)
				sum += Map[seq1[i]][0];
			Max = max(Max,sum);
			return ;
		}
		int limi = n1 - n2 + id2,tsum = sum;
		for(int i = id1;i <= limi;i ++)
		{
			if(i > id1)
				tsum += Map[seq1[i-1]][0];
			dfs(i + 1 , id2 + 1 , tsum + Map[seq1[i]][seq2[id2]]);
		}
	}
}

int main()
{
	freopen("./1080.in" , "r" , stdin);
	int T,i,j;
	char c;
	cin>>T;
	while(T --)
	{
		scanf("%d%c",&n1,&c);
		for(i = 1;i <= n1;i ++)
		{
			scanf("%c",&c);
			seq1[i] = ref(c);
		}
		scanf("%d%c",&n2,&c);
		for(i = 1;i <= n2;i ++)
		{
			scanf("%c",&c);
			seq2[i] = ref(c);
		}
		if(n1 < n2)
		{
			for(int i = 1;i <= n1;i ++)
				swap(seq1[i] , seq2[i]);
			for(int i = n1 + 1;i <= n2;i ++)
				seq1[i] = seq2[i];
			swap(n1 , n2);
		}
		Max = -MAX_INT;
		dfs(1,1,0);
		cout<<Max<<endl;
	}
	return 0;
}

之后冥思苦想了好久，两个序列，开始没有想到变形的LCS（最长公共子序列），只是试着写状态转移方程，最后就写成了那个dp[i][j] = max(dp[i-1][j-1] `,dp[i-1][j]`````,dp[i][j-1])的样子，这时一看才明白这是LCS思想，但是一开始确实是瞎写的，可能碰巧了吧=。=，最后注意这种情况:dp[0][x]，当一个序列之前都用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
/*
poj   1080
268K	0MS	
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 105
#define MAX_INT 2147483647

using namespace std;

int Map[5][5] = {
				{0,-3,-4,-2,-1},
				{-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5},
				};
int seq1[MAXN],seq2[MAXN],dp[MAXN][MAXN],n1,n2;

int ref(char c)
{
	switch (c)
	{
		case 'A':
			return 1;
		case 'C':
			return 2;
		case 'G':
			return 3;
		case 'T':
			return 4;
	}
}

int calc()
{
	memset(dp , 0 , sizeof(dp));
	for(int i = 1;i <= n1;i ++)
		dp[i][0] = dp[i-1][0] + Map[seq1[i]][0];
	for(int i = 1;i <= n2;i ++)
		dp[0][i] = dp[0][i-1] + Map[0][seq2[i]];
	for(int i = 1;i <= n1;i ++)
		for(int j = 1;j <= n2;j ++)
			dp[i][j] = max(dp[i-1][j-1] + Map[seq1[i]][seq2[j]] ,
				max(dp[i-1][j] + Map[seq1[i]][0] , dp[i][j-1] + Map[0][seq2[j]]) );
	return dp[n1][n2];
}

int main()
{
	int T,i,j;
	char c;
	cin>>T;
	while(T --)
	{
		scanf("%d%c",&n1,&c);
		for(i = 1;i <= n1;i ++)
		{
			scanf("%c",&c);
			seq1[i] = ref(c);
		}
		scanf("%d%c",&n2,&c);
		for(i = 1;i <= n2;i ++)
		{
			scanf("%c",&c);
			seq2[i] = ref(c);
		}
		cout<<calc()<<endl;
	}
	return 0;
}
发表更新算法设计

POJ 1789 Truck History

Prim 最小生成树模板，直接上代码

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
/*
poj 1789
16004K	344MS
*/
#include<cstdio>
#include<iostream>
#include<cstring>

#define MAXN 2005

using namespace std;

int n,gra[MAXN][MAXN],low_cost[MAXN];
char str[MAXN][8];

void init()
{
	for(int i = 1;i <= n;i ++)
	{
		for(int j = i + 1;j <= n;j ++)
		{
			int cnt = 0;
			for(int k = 0;k < 7;k ++)
				cnt += (str[i][k] != str[j][k]);
			gra[i][j] = gra[j][i] = cnt;
		}
	}
	for(int i = 1;i <= n;i ++)
		low_cost[i] = 0xfffffff;
}

int calc()
{
	bool mark[MAXN] = {false};
	int sum = 0,s = 1,m = 1,tmin = 0xfffffff,ti = 0;
	mark[s] = true;
	while(m < n)
	{
		tmin = 0xfffffff; ti = 0;
		for(int i = 2;i <= n;i ++)
		{
			if(!mark[i] && low_cost[i] > gra[s][i])
				low_cost[i] = gra[s][i];
			if(!mark[i] && tmin > low_cost[i])
			{
				tmin = low_cost[i];
				ti = i;
			}
		}
		s = ti;
		mark[s] = true;
		sum += tmin;
		m ++;
	}
	return sum;
}

int main()
{
	while(cin>>n && n)
	{
		memset(gra , 0 , sizeof(gra));
		memset(low_cost , 0 , sizeof(low_cost));
		for(int i = 1;i <= n;i ++)
			scanf("%s",str[i]);
		init();
		printf("The highest possible quality is 1/%d.\n",calc());
	}
	return 0;
}
发表更新随笔杂谈

一些事情

一些事情，看开了一些事情，不算看开吧，只是在事实面前不想做反抗也做不出反抗罢了。

发表更新随笔杂谈

院内 ACM 大赛

今天下午两点到五点，理工配楼二层信息学院ACM大赛，ACMore_txj，ACMore_znc，ACMore_yld，共12道题，三个小时做出四道题，两道一直WA，没过，二等奖。一等奖五道题目。哎，即使不是正规的ACM/ICPC题目，还是感觉到自己太弱了，真的太弱了。仰仗学了不少模板就以为可以变厉害了，其实不是，ACM的题目更多的还是需要思维而不是记忆的，正如ACM朴神说的：“现在ACM模板题目已经不多了，更多的是多种算法思想混杂在一起需要自己去组织”。真的不能再沉迷在POJ排名上了，现实说明你仍然是以前那个蒟蒻，你的实力并没有提高多少，无非就是见得多一点，仅此而已。至于怎么真正提升自己，我不知道，我真的不知道，得过且过？还是由算法研究转向应用呢？真的想要动摇了，毕竟不是ACM队的，又何必？

发表更新随笔杂谈

总结 & 反思

刚刚过掉一道题，这题是上学期接触编程不久后做出来的，但是刚刚在做的时候却一直WA，脑海里一直想着当初是怎么1A的，尽量去揭开那时的记忆拿到算法，但是总想不出来，过了好久还是没过，只能打开以前的文件夹看了一下以前的做法，我现在的做法和那时几乎相同，但是有一步比较关键的没想到。也许是看不起那时的自己，认为那时能A的题目现在一定能A，但是事实说明，目前好像有点自信心过于膨胀了。POJ上连续刷了半个学期的题目，一口气看了很多算法和数据结构，就认为自己已经变牛了，可事实说明，你还是当初那个什么都不懂的你。圣人尚自谦，何况你还不是圣人，何况这一行有那么多的惊才绝艳的天才妖孽，你凭什么飘飘然？脚踏实地才是王道，学院ACM队的大牛现在仍是我不可企及的目标，何况还有国家队的大神呢？

好了，清醒一下，后天就是学院举行的程序设计大赛，争取拿个好成绩吧。

发表更新算法设计 / 技术学习

字典树

字典树，就是一种最大限度的利用单词的公共前缀高效查询单词（但不止是单词，所有有前缀的都可以类似进行查找）的数据结构。节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node
{
    node *next[26];//26个字母，NULL则表示没有相应字母的分支
    bool isWord;//true表示从根节点到当前节点路途中所有字母连成的单词已经在字典中
    int point;//指向单词的信息域（如释义等）
    node()//初始化函数
    {
        for(int i = 0;i < 26;i ++)
            next[i] = NULL;
        isWord = false;
        point = 0;
    }
}

建树和查询都非常方便，删除操作并不常用，比较偷懒的方法就是找到待删除单词的最后一个字母所在节点，把isWord标记置为false即可。代码就不给出了。

需要注意的是，在实际建树过程中，如果动态分配空间无论是new还是malloc都会很慢，一般都会TLE的，所以代码都是静态实现，即先分配一定的空间，需要用新节点时就从空间里拿。

例题:

一、POJ 2503 Babelfish

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
/*
poj  2503
17664K	235MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 150005

using namespace std;

struct node
{
	node *next[26];
	bool isWord;
	int point;//不在结构体内设置字符数组而是模拟一个指针指向储存区这样可以节省不少空间 
	node()
	{
		for(int i = 0;i < 26;i ++)
			next[i] = NULL;
		isWord = false;
		point = 0;
	}
}all[MAXN];

int index = 1,size;
char store[100005][11];

void insert(char *str1,char *str2)
{
	node *tmp = &all[0];
	int len = strlen(str1);
	for(int i = 0;i < len;i ++)
	{
		int num = str1[i] - 'a';
		if(!tmp->next[num])
			tmp->next[num] = &all[index++];
		tmp = tmp->next[num];
	}
	tmp->isWord = true;
	size ++;
	tmp->point = size;
	strcpy(store[size] , str2);
}

void find(char *s)
{
	node *tmp = &all[0];
	int len = strlen(s);
	for(int i = 0;i < len;i ++)
	{
		int num = s[i] - 'a';
		if(!tmp->next[num])
		{
			printf("eh\n");
			return ;
		}
		tmp = tmp->next[num];
	}
	if(tmp->isWord)
		printf("%s\n",store[tmp->point]);
	else
		printf("eh\n");
}

int main()
{
	char str1[12] = {0},str2[12] = {0},s[24];
	while(gets(s) && s[0])
	{
		sscanf(s,"%s %s",str1,str2);
		insert(str2,str1);
	}
	while(scanf("%s",s) != EOF)
	{
		find(s);
	}
	return 0;
}

二、POJ 3630、Phone List

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
/*
poj 3630
4628K	219MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 100005

using namespace std;

struct alp
{
	char s[11];
}per[MAXN / 10 + 5];

struct node
{
	bool isWord;
	node *next[10];
	node()//初始化函数很重要！ 
	{
		isWord = false;
		for(int i = 0;i < 10;i ++)
			next[i] = NULL;
	}
}all[MAXN];

bool cmp(alp a,alp b)
{
	return strlen(a.s) < strlen(b.s);
}

void doIt()
{
	memset(all , 0 , sizeof(all));
	int n,index = 0;
	cin>>n; node *root, *tmp;
	root = &all[index++];
	for(int i = 1;i <= n;i ++)
		scanf("%s",per[i].s);
	sort(per + 1 , per + n + 1 , cmp);
	//要先按字符串长度从小到大排序，不然对于 12  1之类的数据会出错 
	for(int p = 1;p <= n;p ++)
	{
		tmp = root;
		int len = strlen(per[p].s);
		for(int i = 0;i < len;i ++)
		{
			int num = per[p].s[i] - '0';
			if(tmp->next[num])
			{
				if(tmp->next[num]->isWord)
				{
					printf("NO\n");
					return ;
				}
			}
			else
				tmp->next[num] = &all[index++];
			tmp = tmp->next[num];
		}
		tmp->isWord = true;
	}
	printf("YES\n");
	return ;
}

int main()
{
	int T;
	cin>>T;
	while(T --)
	{
		doIt();
	}
	return 0;
}
发表更新转载文章

注做好一件事

作者: JACK ALTMAN 来源: 36氪

1
2
人们对机会的估值过高，这是我在下棋的时候学到的一点。你其实只需要一个好的选择就行，没必要同时去追求 A、B、C、D
——Peter Thiel

是让你的选择尽可能开放，还是全心全意抓住一个选择，专心做好一件事情——可以说这两者之间的权衡，是我们生活中经常会碰到的。我们自打上学起，就一直被教育不要去做那些可能会断了某条路的决定。

这种让未来保持开放，让自己未来拥有更多选择和出路也是可以理解的。握在手中的成功机会越多，你的未来也就会越成功，不是吗？

不细想可能会觉得保持开放的确很好，但我认为事情并非看上去那么简单，原因如下：

  1. 明星效应。很简单，在一个领域保持顶尖水平，比在一两个领域保持领先水平和五六个领域保持一般水准都要更有价值、并且收益更好。
  2. 有悖常识的真相：让未来更开放的方式，正是专注的去做好一件事情。这个世界上最成功的人，他们在某一领域获得成功之后，可通过经营杠杆进入任何他们想要涉足的领域。而这都得依赖于他们曾极致的专注在做好一件事情上。

我时常会将这个权衡同创业公司连系起来思考。在创立一家公司时，创始人也会面临这个权衡，究竟是让未来更加多元，更开放，同时追求好几个选择，还是专注的做好其中一个。而通常，最好的创业公司都会选定一个，然后寻找一切方法让它成为现实。自然，也有很多创业公司他们并不清楚未来的路，他们相信手中握有的诸多好的选择中，总有一两个能行得通。

记住，在某一个水平上，你一次只能做好一件事情。能够拿到你最想去的学校和公司的 Offer，比拿到在你 Reference 排名中名列 2-5 位的 Offer 要好。而在一件事情上能够做到 99%，也比在 2 件事情上都能做到 90%，或者 3 件事情上做到 80% 要强很多。

如果你可以在不失专注的情况下够获得一些机会，那就抓住它们。这里我并不是宣扬你得故意同机会保持距离。我要做的就是让人们开始重视专注，因为同 Peter Thiel 一样，我也认为人们普遍高估了机会的价值。

发表更新算法设计

POJ 2251 Dungeon Master(BFS例题)

用STL的queue实现BFS，最基础的题目了，不多说上代码

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
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 35

using namespace std;

int lv,n,m,sta_x,sta_y,sta_z;
char maze[MAXN][MAXN][MAXN];
int op[7][3] = {{0,0,0},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
bool mark[MAXN][MAXN][MAXN];

struct node
{
	int z;
	int x;
	int y;
	int step;
};

void find_point()
{
	for(int i = 0;i < lv;i ++)
	{
		for(int j = 0;j < n;j ++)
		{
			for(int k = 0;k < m;k ++)
			{
				if(maze[i][j][k] == 'S')
				{
					sta_x = j; 
					sta_y = k;
					sta_z = i;
				}
			}
		}
	}
}

void bfs()
{
	bool flag = false;
	memset(mark , false , sizeof(mark));
	mark[sta_z][sta_x][sta_y] = true;
	queue<node>myQueue;
	node st;
	st.z = sta_z; st.x = sta_x; st.y = sta_y; st.step = 0;
	myQueue.push(st);
	while(!myQueue.empty())
	{
		node tmp = myQueue.front();
		myQueue.pop();
		for(int i = 1;i <= 6;i ++)
		{
			int tz = tmp.z + op[i][0];
			int tx = tmp.x + op[i][1];
			int ty = tmp.y + op[i][2];
			if(tz >=0 && tz < lv && tx >=0 && tx < n && ty >=0 && ty < m && !mark[tz][tx][ty])
			{
				if(maze[tz][tx][ty] != '#')
				{
					if(maze[tz][tx][ty] == 'E')
					{
						printf("Escaped in %d minute(s).\n",tmp.step + 1);
						return ;
					}
					mark[tz][tx][ty] = true; node now;
					now.z = tz; now.x = tx; now.y = ty;
					now.step = tmp.step + 1;
					myQueue.push(now);
				}
			}
		}
	}
	printf("Trapped!\n");
}

int main()
{
	while(cin>>lv>>n>>m && (lv || n || m))
	{
		for(int i = 0;i < lv;i ++)
			for(int j = 0;j < n;j ++)
				scanf("%s",maze[i][j]);
		find_point();
		bfs();
	}
	return 0;
}
发表更新算法设计 / 技术学习

由二叉树的两个遍历序列求另一个遍历序列

二叉树的重要的遍历序列有三种：先序遍历，中序遍历，后序遍历。其中中序遍历可以由其他两种遍历序列定位的根来划分出左右两棵子树，所以已知的两种遍历序列中必须有中序遍历。

示意图（先序+中序->后序）

示意图

对于先序遍历序列，树根一定是第一个元素（后序遍历的根则是最后一个），知道树根后在中序遍历中找到树根，则根前面的就是左子树，后面的就是右子树，再递归的对左右子树执行上述操作直到序列为空，输出序列就是另一种序列。对于求先序序列，每次都是找到树根就输出，而求后序序列时是先递归处理完左右子树后再输出根。

代码：

输入中序和后序，求先序

输入：

DBKFIAHEJCG
DKIFBHJEGCA

输出：

ABDFKICEHJG

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
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 150

using namespace std;

char in[MAXN],post[MAXN];

void make_pre(char *a,char *b,int len)
{
	cout<<b[len-1];
	int le1 = 0,le2 = 0;
	for(int i = 0;i < len;i ++,le1 ++)
		if(a[i] == b[len-1])
			break;
	le2 = len - le1 - 1;
	if(le1 > 0)
		make_pre(a,b,le1);
	if(le2 > 0)
		make_pre(&a[le1+1],&b[le1],le2);
}

int main()
{
	freopen("./tree_trans.in" , "r" , stdin);
	cin>>in>>post;
	make_pre(in,post,strlen(in));
	return 0;
}

输入中序和先序，求后序

输入：

DBKFIAHEJCG
ABDFKICEHJG

输出：

DKIFBHJEGCA

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
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 150

using namespace std;

char in[MAXN],pre[MAXN];

void make_post(char *a,char *b,int len)
{
	int le1 = 0,le2 = 0;
	for(int i = 0;i < len;i ++,le1 ++)
		if(a[i] == b[0])
			break;
	le2 = len - le1 - 1;
	if(le1 > 0)
		make_post(a,&b[1],le1);
	if(le2 > 0)
		make_post(&a[le1+1],&b[le1+1],le2);
	cout<<b[0];
}

int main()
{
	freopen("./tree_trans.in" , "r" , stdin);
	cin>>in>>pre;
	make_post(in,pre,strlen(in));
	return 0;
}
发表更新算法设计

堆和堆排序

所谓堆，就是一棵完全二叉树，对于二叉树的任意一个节点node,它的左右孩子（如果有的话）都和node满足同一种关系，如都大于node（小根堆）或都小于node（大根堆），但是左右孩子之间的关系没有要求。通常用数组来实现一个堆，对于每一个节点，它的下标2就是左孩子（如果有的话），左孩子下标再加一就是右孩子（如果有的话），操作起来很方便。堆的构造是每插入一个元素都对元素进行适当的上浮调整，使之满足堆的条件，时间复杂度为O(nlogn)。如果每次删除堆顶并输出，并将堆的最后一个元素移到堆顶后再对其进行下沉调整重新形成一个堆，循环操作直到堆为空，那么最后输出的序列一定是有序的，这就是堆排序。

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
堆和堆排序
*/
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 100005
#define MAX_INT 2147483647
#define FA(x) (x>>1) 
#define LC(x) ((x<<1))
#define RC(x) ((x<<1)|1)
#define MID(x,y) ( (x + y) >> 1 )
#define TIME_BEGIN double t1 = clock()
#define TIME_END double t2 = clock();printf("\n%.2lfms\n",t2-t1)

using namespace std;

int size,top = 1;
int heap[MAXN];

bool cmp(int a,int b)//关键字比较函数，目前是构造小根堆 
{
	return a < b;
}

void up(int id)//上浮操作 
{
	if(id == 1)
		return ;
	if(!cmp(heap[FA(id)] , heap[id]))
	{
		swap(heap[FA(id)] , heap[id]);
		up(FA(id));
	}
}

void down(int id)//下沉操作 
{
	if(RC(id) <= size)//当前节点有左右孩子 
	{
		if(cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
		else if(!cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[RC(id)] , heap[id]))
		{
			swap(heap[RC(id)] , heap[id]);
			down(RC(id));
		}
	}
	else if(LC(id) <= size)//当前节点只有左孩子 
	{
		if(cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
	}
}

void insert(int t)//插入新元素 
{
	heap[++size] = t;
	up(size);//上浮调整堆 
}

int dele()//删除并返回堆顶 
{
	int tmp = heap[top];
	heap[top] = heap[size--];
	down(top);//下沉调整堆 
	return tmp;
}

void print(int num)//按层遍历 
{
	int k = 1,cnt = 0,kk = 0;
	while(num)
	{
		num -= k;
		while(kk < k)
		{
			cnt ++; kk ++;
			cout<<heap[cnt]<<" ";
		}
		kk = 0;
		cout<<endl;
		k = min(k<<1, num);
	}
}

int main()
{
	TIME_BEGIN;
	freopen("./heap.in" , "r" , stdin);
	int t;
	while(cin>>t)
	{
		insert(t);//插入堆元素 
	}
	print(size);//按层遍历整个堆 
	cout<<"==============="<<endl;
	while(size)
	{
		cout<<dele()<<" ";//依次弹出堆顶进行排序 
	}
	cout<<endl<<"==============="<<endl;
	TIME_END;
	return 0;
}

测试数据：15 1 2 9 8 7 6 3 11 13 5 12 4 10 14

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
1
3 2
8 5 4 6
15 11 13 9 12 7 10 14
===============
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
===============

0.00ms

——————————–
Process exited with return value 0
Press any key to continue . . .
关注我

最新文章

分类

标签

三体1
不吐不快4
书单29
分布式1
历史2
同人随笔1
图灵完备1
子夜自话1
容器1
影视评论2
数据库1
算法17
胡思乱想13
计算机学习57
读书笔记129
随笔1

归档

链接

×