Swap(hp[c],hp[v]);swap(pos[hp[c]],pos[hp[v]]);
Pop_down(c);

}

}
7. 二叉堆

查找最大值
即根结点——hp[0]

删除元素
将根结点的值改为无穷小并向下调整，总数减一 或者hp[0]=hp[--S]，并向下调整

插入元素
堆的存储方式——数组 C++的选手可以使用Algorithm内的标准的堆 相关函数 E.g. hp[]记录堆元素 pos[]记录元素在堆中位 置 val[]记录元素的权值 元素个数为S 则对于点 v

v-1>>1 其左孩子为 (v<<1)+1 // 若大于S则不存在 其右孩子为 (v<<1)+2 // 若大于S则不存在
其父亲为
7. 二叉堆
调整元素——将一个元素v 的值变大/变小 Pop_down(v) {

Int c = v, i=(v<<1)+1, j=(v<<1)+2; If(i<S&&val[hp[c]]<val[hp[i]])c=I; If( j<S&&val[hp[c]]<val[hp[ j]])c=j; If(c!=v) {


}
U=find(u); v=find(v); If(rank[u]>rank[v]) swap(u,v); Rank[v]+=rank[u]; fst[u]=v;
5. 并查集
思考题：团伙 城市里有N个人，给出M条信息，每条信息告 诉你两个是朋友还是敌人 一个人朋友的朋友是朋友 一个人敌人的敌人还是朋友 请问这个城市里有多少个团伙？ 或者输出不可能 N,M<500000
即将新元素放在序列末尾并向上调整
7. 二叉堆

实用：
Dijkstra算法的优化 很多最值问题 堆排序 ……
7. 二叉堆
思考题：灌水 有N*M个单位方格的土地，每个方格有一个 正的高度，土地周围都是平地。 一天下了大雨，请问这N*M的土地上一共装 了多少水呢？ 你能利用二叉堆和宽度优先遍历设计出时间复 杂度为O(NMlogNM)的算法吗？

6. LCA
LCA(Lowest Common Ancestor) 最近公共祖先问题：

倍增算法O(NlogN)-O(logN)——在线 区间RMQ算法O(NlogN)-O(1)——在线 区间+1RMQ算法O(N)-O(1)——在线 Tarjan算法O(N+Qα(N))-O(1)——离线
i=S;i>=0;--i)
fa[v][0];
7. 二叉堆
堆是一个特殊的二叉树 每个结点有一个权值 根结点的权值不小于其两个孩子结点的权值 支持操作：

O(logN) 删除一个元素 O(logN) 调整一个元素 O(logN) 寻找最大值 O(1)
插入一个元素
7. 二叉堆

3.如何分辨树

关键词
任意两点只有一条路径 平面每个点只向左连一条边 N个点N-1条边的连通图 ……
4.树遍历
先序遍历 中序遍历 后续遍历 层次遍历

对应了搜索问题——搜索问题即在一颗搜索 树上进行遍历
4.1深度优先遍历
分析遍历序列的性质 先序遍历：

aBC



}e[MaxE]; Int head[MaxN], tot; // head初始值为-1 Int Insert(u, v) {
} 遍历： For(int i=head[u];i!=-1;i=e[i].nxt)

Int u, v, nxt; Inline edge(int u=0, int v=0, int nxt=-1):u(u),v(v),nxt(nxt){};
If(P&1<<i) v=fa[v][i];
i=0;i<S;++i)


求公共祖先

For(int

Lca(u, v) {// dep[u]<dep[v]
Go_up(v,dep[v]-dep[u]);

}// O(logN)
Return
If(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
E[tot]=edge(u,v,head[u]);head[u]=tot++;
5. 并查集

支持操作：
合并两个集合 查找集合的代表元素

实现方式：父亲记录法
用一棵树来表示一个集合 根作为集合的代表元素 合并即将一个集合的根指向另一个集合的根
5. 并查集

优化：
按秩合并
每次总是将点的个数小的那个集合的根指向点数较多的

中序遍历：
BaC
后序遍历： 可以发现在DFS遍历序列中一棵子树必然是连 续一段，因此子树可以和区间相对应
BCa
4.2宽度优先遍历
和图的宽度优先遍历一致 使用队列 优点：

不使用栈空间
速度快 遍历序列即为层次拓扑序列
4.3 树遍历的若干技巧



由于树的稀疏性，请使用邻接表来存储树 邻接表并不需写链表，建议使用数组模拟链表 struct edge {
6.LCA
倍增算法： Dep[v]记录v的深度 Fa[v][k]记录v向上第2k个祖先 预处理：

Fa[v][k]=fa[fa[v][k-1]][k-1]

时空复杂度 O(NlogN)
6.LCA

v向上走p层

For(int

Go_up(&v,p) {
} // O(logN)
那个集合的根
路径压缩
即在寻找根的过程中，将所有指针经过的结点都直接指

向根
5. 并查集
C++代码:fst记录父亲，rank记录点的个数 int find(v) {

} Int unite(int u, int v) {


If(fst[v]==v) return v; Else return (fst[v]=find(fst[v]))
2010山东夏令营
Author : Will
树与二叉树的常用算法
1. 定义
树：要么为空，要么由根结点(root)和n棵子 树组成。 森林：若干棵树 二叉树：递归定义

要么为空，要么由根结点左子树和右子树组成 左右子树都是一颗二叉树
2.树与二叉树的转化
左儿子右兄弟表示法 这样的好处是在很多树形动态规划问题中能大 大降低编程复杂度和算法的时间复杂度