dijkstra(最短路)和Prim(最小生成树)下的堆优化
最小堆:
down(i)【向下调整】:从第k层的点i开始向下操作,第k层的点与第k+1层的点(如果有)进行值大小的判断,如果父节点的值大于子节点的值,则修改,并继续对第k+1层与第k+2层的点进行判断和修改,否则不修改,且退出。当点向下移动到树的最后一层,没有子节点供判断与修改,停止操作。
树最多有log(n) 层[log(n)=log2n,一般省略数字2],时间复杂度log(n)次。
up(i)【向上调整】:同理,时间复杂度log(n)次。
1.求n个数进行排序:
I.建树(n/2次down):
for i←n/2 downto 1 do down(i)
II.取数(n次down):
for i←1 to n do
temp←a[1];
a[1]←a[n];
a[n]←temp;
n←n-1;
down(1);
所以时间复杂度:O(nlogn)
2.dijkstra , prim 需要修改数,取数多少次?
I.dijkstra:
从点x出发到点y(或其它剩余点)的最短路:
dist[t]:点t到点x的最短距离,若点t不能到达点x,则值为无穷(设为一个足够大的值,如2000000000)。初始时dist[x]=0,其它点dist[]=无穷。
初始:d=x。
1.遍历所有与点d相关联的边,修改与d点相邻的点的最短距离(到x点)。
2.在未执行1操作的点中找到最短距离(到x点)的点d。
3.重复1,2操作,直到2操作d=y,或者执行n-1次(总共n个点,那么求的是从x点到其它点的最短路)。
时间复杂度:
最多执行n-1次操作,而操作1,2时间复杂度O(n),时间复杂度O(n^2)。
堆优化:
初始时,把所有的dist[k](k=1,2,……,n)建最小堆。对于操作1,修改堆中某些数(dist[])的值,并对这些数的位置进行修改(距离是越来越短,所以进行向上调整);
对于操作2,把堆中第一个数(最小值)取出,删除根结点,把最后一个元素作为根结点,然后对根节点进行向下调整,保证调整后的根节点为树中的最小点。
时间复杂度:
建堆n个数,时间复杂度O(nlogn)
取数n-1次,而堆中节点个数总小于等于n(最多有n个dist[]),时间复杂度O(nlogn)。
最坏的情况:
如下图(可删去部分边),与点k相邻的边(边另外的点的编号小于k)的长度为k,求从n点出发到y点,从点n出发到点1,则所有的边都会被修改为dist[]的值一次,修改e次,则时间复杂度O(eloge),其中e为边的数目。
总时间复杂度O(nlogn+elogn)。
若图是稠密图,e很大,如n<=10000,而e<=n*(n-1)/2,若e= n*(n-1)/2,nlogn+elogn <664452058,而n*n=100000000,则该优化比原来时间复杂度还高不少。
若图是稀疏图,e不大,如n<=10000,e<=100000,则elogn<1328772,n*n=100000000,此时用该优化不会超时而用原方法会超时。
更好的优化:斐波那契堆(不涉及删除元素的操作仅需O(1)的平摊运行时间)
取数n-1次(删除+修改),而堆中节点个数总小于等于n(最多有n个dist[]),时间复杂度O(nlogn)。
修改e次数值,时间复杂度O(e)。
总时间复杂度:O(nlogn+e)。
II.Prim:
求最小生成树
dist(t):点t到集合S中的点的最短距离,该最短距离为其中一条边的长度,若点t不能到达任意一个点,则值为无穷(设为一个足够大的值,如2000000000)。初始时dist[x]=0,其它点dist[]=无穷。
从任意一个点x出发,初始:d=x,S=空集【S为集合】,T=全集。
1.S=S+{d},T=T-{d},遍历所有与点d相关联的边,修改集合T中的点的dist值。
2.从点T中找到dist[]值最小对应的点d,图添加一条边,该边的长度为dist[d]。可以添加一个变量记录边的另外一个点。
3.重复1,2操作,直到执行n-1次(即添加n-1条边)。
时间复杂度:最多执行n-1次操作,而操作1,2时间复杂度O(n),时间复杂度O(n^2)。
堆优化:
初始时,把所有的dist[k](k=1,2,……,n)建最小堆。对于操作1,修改堆中某些数(dist[])的值,并对这些数的位置进行修改(距离是越来越短,所以进行向上调整);
对于操作2,把堆中第一个数(最小值)取出,删除根结点,把最后一个元素作为根结点,然后对根节点进行向下调整,保证调整后的根节点为树中的最小点。
时间复杂度:同理总时间复杂度O(nlogn+elogn)。
斐波那契堆优化:O(nlogn+e)。
另外的方法(不一样的角度):
dist(t):点t到集合S中的点的最短距离,该最短距离为其中一条边的长度,若点t不能到达任意一个点,则值为无穷(设为一个足够大的值,如2000000000)。初始时dist[x]=0,其它点dist[]=无穷。
从任意一个点x出发,初始:d=x,S=空集【S为集合】,T=全集。R=空集。
1.S=S+{d},T=T-{d},遍历所有与点d相关联的边,若某条边的另外一个点在T集合而不是在S集合,则把该边加入集合R中。
2.从集合R中找到长度最小的且边有一个点在T集合(边的另外一个点必在S集合)的边,d=边的两点中的在T集合的点。图添加一条边,该边的长度为dist[d]。可以添加一个变量记录边的另外一个点。
3.重复1,2操作,直到执行n-1次(即添加n-1条边)。
堆优化:
把边加入堆中,时间复杂度O(eloge)。
取边n-1次,时间复杂度O(nloge)。
[事实上每次堆的数目小于等于e]
总时间复杂度O(nloge+eloge)。
无疑,该方法比上述方法时间复杂度要高。
c++用优先队列更好,见:
http://www.cnblogs.com/cmyg/p/8725042.html