数据结构(2)acwing

1.trie树
- 快速存储和查找字符串的集合
- 结构特征:

- 例题:Trie字符串统计 ?
2.并查集(近乎O(1))
- 将两个集合合并
- 询问两个元素是否在一个集合中
- 问题1:如何判断树根:if(p[x] == x)
- 问题2:如何求x的集合编号:while(p[x] != x) x = p[x];
- 问题3:如何合并两个集合:px是x的集合编号,py是y的集合编号。p[x] = y,直接上图

优化:
1.路径压缩
- scanf使用%s会默认忽略“空格”和"回车",不用%c
- 上代码:

3.堆
- 概念:”小根堆“(顾名思义{根小于左右儿子})----》为“完全二叉树”(最后一行可以不满,以上全满),上图

-
存储方式(一维数组存储)

-
如何手写一个堆?
-
插入一个数
heap[ ++ size] = x;up(size);
-
求集合中最小值
heap[1];
-
删除最小值
heap[1] = heap[size];size --;down(1);
-
删除任意一个元素
heap[k] = heap[size];size --; down(k);up(k);
-
修改任意一个元素
heap[k] = x;down(k);up(k);
原文链接:http://www.cnblogs.com/happy-prince/p/14939025.html