Trie:高效地存储和查找字符串集合的数据结构
并查集:
1、将两个集合合并
2、询问两个元素是否在一个集合当中
并查集可以在近乎O(1)的时间内完成这两个操作
基本原理：每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点
问题1：如何判断树根:if(p[x] == x)
问题2：如何求x的集合编号:while(p[x] != x) x = p[x];
问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x] = y
优化：路径压缩、安置优化（不常用 不讲）
这里的堆是手写模拟 STL中的堆是优先队列 priority queue
堆：是一个完全二叉树：除了最后一层节点之外 上面的所有节点都是满的 最后一层节点是从左到右排列
小根堆为例：每一个点都是小于等于左右儿子的
如何手写一个堆：
1.插入一个数 heap[++size] = x; up(size);
2.求集合当中的最小值 heap[1];
3.删除最小值 heap[1] = heap[size]; size--; down(1);
让堆最后一个元素来覆盖堆顶的元素 然后size-- 再堆顶down一下就可以了
4.删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k);
5.修改任意一个元素 heap[k] = x; down(k); up(k);
Trie: 高效地存储和查找字符串集合的数据结构
并查集:
1、将两个集合合并
2、询问两个元素是否在一个集合当中
并查集可以在近乎 O (1) 的时间内完成这两个操作
基本原理：每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p [x] 表示 x 的父节点
问题 1：如何判断树根: if (p [x] == x)
问题 2：如何求 x 的集合编号: while (p [x] != x) x = p [x];
问题 3：如何合并两个集合：px 是 x 的集合编号，py 是 y 的集合编号。p [x] = y
优化：路径压缩、安置优化（不常用 不讲）
这里的堆是手写模拟 STL 中的堆是优先队列 priority queue
堆：是一个完全二叉树：除了最后一层节点之外 上面的所有节点都是满的 最后一层节点是从左到右排列
小根堆为例：每一个点都是小于等于左右儿子的
如何手写一个堆：
1. 插入一个数 heap [++size] = x; up (size);
2. 求集合当中的最小值 heap [1];
3. 删除最小值 heap [1] = heap [size]; size--; down (1);
让堆最后一个元素来覆盖堆顶的元素 然后 size-- 再堆顶 down 一下就可以了
4. 删除任意一个元素 heap [k] = heap [size]; size--; down (k); up (k);
5. 修改任意一个元素 heap [k] = x; down (k); up (k);
