堆（STL中的优先队列）
优先队列：在队列中，元素被赋予优先级，优先级最高的最先被弹出
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
//STL中的优先队列默认以大为优先级
priority_queue<int> q1;
q1.push();//push a element into the queue
q1.top();//botain the top element
q1.empty();//the queue is empty?
q1.size();//inquire the queue size
q1.pop();//delete the top element in queue
//下面这个是小顶堆，以小为优先级
priority_queue<int, vector<int>, greater<int> > q2;
}学习堆
在学习堆之前，我们要知道什么叫完全二叉树
二叉树：指树种的节点的度不大于2的有序树
-
结点的度：一个节点拥有子树的数目 成为 结点的度
-
节点名称：左子节点，右子节点，父节点
-
结点层次：根节点为1，根节点的子节点为2，以此类推
-
树的深度：树的高度，也是层次的最大值
?
完全二叉树：深度为k，有n个结点的二叉树，当且仅当每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树，如图所示
通俗来讲，除了最深层，其他所有层数的结点都是满的，最深层的结点从左到右，编号递增排列
?
?
实现完全二叉树
用数组实现
注意下标从1开始
// 设当前结点编号为i，其左子节点编号为lson，其右子节点编号为rson，其父节点编号为fa
int lson = i << 1;
int rsom = i << 1 | 1;
int fa = i >> 1;
//根节点是没有父节点的模拟堆
构建一个小根堆
//1读入
int n;
for(int i = 1; i <= n; i++)
cin >> h[i];
len = n;
for(int i = n/2; i; i--) down(i);
//2插入
Insert(x);插入
-
Insert
void Insert(int x)
{
len ++;
h[len] = x;
up(len);
}-
down
void down(int index)
{
int t = index;
int lson = t << 1, rson = t << 1 | 1;
if(lson <= len && h[lson] < h[t]) t = lson;
if(rson <= len && h[rson] < h[t]) t = rson;
if(t != index)
{
swap(h[t], h[index]);
down(t);
}
}-
up
void up(int index)
{
if(index >> 1 > 0 && h[index] < h[index >> 1])
{
swap(h[index], h[index >> 1]);
up(index >> 1);
}
}删除
//删除头部
void pop_top()
{
h[1] = h[len];
len--;
down(1);
}
//删除任意
void Delete(int index)
{
h[index] = h[len];
len--;
down(index);
up(index);
}给出一道题 可以自行联系模拟堆的部分操作
在实际做题中，很少使用手写堆，而是使用STL中的priority_queue
----------------------------------------------------------------------------------
并查集
现在有一个问题：给出n个点和m条边的无向图，询问任意两点是否连通
我们能想到的比较朴素的算法就是dfs搜索 看一下能不能搜到，时间复杂度是o(n)
引入并查集
并查集可以在将近o(1)的情况下来查询两个点是否处于一个集合中
应用
-
合并：把两个不相交的集合合并为一个
-
查询：查询两个集合是否在同一集合中
我们可以这样想象
一开始有n个人，这n个人一开始只有一个老大，就是自己
?
在争夺地盘的时候，逐渐形成了帮派
有的人开始认老大，有的人收小弟
?有的老大在抢地盘的时候败北，带着自己的小弟全部投靠了那位老大
?
这里需要非常注意的是：
-
只能是一个老大带领小弟并入别的帮派，因为只有老大才能代表着一个帮派的行为
-
如上图，6号结点的顶头上司还是4号结点，只是6号结点的最终老大是1号。因此在查询的时候就得一层一层地往上询问老大是谁
简述一下代码思路
利用树来存储每一个集合，用树根（老大）的编号来代表整个集合的编号。每个节点存储他的父节点，例如p[x]就是x的父节点。
问题1：如何判断树根?
答;自己的老大是自己的人，就是树根，也就是根节点
If(fa[x] == x)问题2：如何求x的集合编号？
答：通俗的说，从x一路向上直到树根。
while(fa[x] != x) x = fa[x];问题三：如何查询x和y是否在一个集合里？
答：fa[x] == fa[y] 代表x和y在同一个集合
问题四：如何合并两个集合？
答：加一条边（一个集合的根节点的父节点为另一个集合的根节点）
fa[x] = y;我们讨论一种极端情况
在上面的问题2中，出现了这样的情况
-
一个帮派非常非常多人
-
帮派的人所形成的关系是一种线性的，那么他的查询时间将会是o(n)，反复查询的话时间复杂度太大，没有达到预想中的效果
根据上述情况，我们提出了名叫路径压缩的方法
在每次查询的时候，把路径上的点的父亲改成根节点，以便于以后再查询
模板如下
void find(int x)
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}并查集裸题
这里有并查集的基本使用方法