离散堆
在Dijkstral与Prim这两个O(n^2)的算法中，我们需要一个很快的东西来取到最小的mindist（否则存在O(mlogm)与O(km)的Spfa与Kruskal时，他们就没有很大的用武之地了）。
我们自然想到用堆来取到最小的mindist。但是由于堆会使得每一个节点的位置不在是它的节点的信息，因此我们需要一个离散堆。
离散堆多了一个PIH数组（个人用此变量名的原因是'Position in Heap'）。
在接下来的叙述中，我们以Prim为例叙述，我们令
Heap:Array[//] of Record={pnum,dist:Longint}
PIH:Array[//] of Longint
堆中的pnum记录当前堆节点记录的是图中哪个点，dist记录当前堆中pnum这个点的距离dist（与普通Prim的Dist数组一样，只是跟着pnum在动）。PIH[x]记录x这个点在Heap中的位置，如果PIH[x]=0说明x这个点不在堆中。
堆元素交换
堆的操作离不开交换，但是此时我们交换的不仅是一个值了，我们需要交换Heap.pnum与Heap.Dist，以及对应的PIH。所以我们交换堆中的元素，不能普通交换。
假设我们要交换px与py这两个位置的元素。
先找到并交换PIH[px]与PIH[py]。
之后交换Heap[px]与Heap[py]中的所有元素。
代码如下：
procedure swap(var a,b:longint);
procedure Heapswap(var px,py:longint);//交换px与py的位置
var
tx,ty:longint;//tx与ty是对应的图中的点
begin
if px=py then exit;
tx:=Heap[px].pnum;
ty:=Heap[py].pnum;
swap(PIH[tx],PIH[ty]);//先修改PIH
swap(Heap[px].pnum,Heap[py].pnum);//再修改Heap
swap(Heap[px].Dist,Heap[py].Dist);
end;
上调与下调
堆的上调与下调还是一样的，但是在交换的时候调用Heapswap(px,py)即可。
上调代码：
procedure UP(p:longint);
var
j:longint;
begin
j:=p shr 1;
while j>=1 do
if Heap[p].Dist<Heap[j].Dist then
begin
Heapswap(p,j);
p:=j;
j:=j shr 1;
end
else j:=0;
end;
下调代码：
procedure Down(p:longint);
var
j:longint;
begin
j:=p shl 1;
while j<=top do
begin
if (j<top) and (Heap[j].Dist>Heap[j+1].Dist) then inc(j);
if Heap[p].Dist>Heap[j].Dist then
begin
Heapswap(p,j);
p:=j;
j:=j shl 1;
end
else j:=top+1;
end;
end;
插入与删除
插入与删除与原来的没有什么区别。
删除注意先交换，再更新PIH（令PIH为0），最后调整堆。
插入注意先令PIH，再调整堆。
插入代码：
procedure Ins(x,w:longint);
begin
inc(top);
Heap[top].pnum:=x;
Heap[top].Dist:=w;
PIH[x]:=top;
UP(top);
end;
删除代码：
procedure Delete(p:longint);
begin
Heapswap(top,p);
PIH[Heap[top].pnum]:=0;
Heap[top].pnum:=0;
Heap[top].Dist:=0;
dec(top);
if p<>top+1 then//如果UP或者Down带了max，就不必这样判断了。
begin
UP(p);
Down(p);
end;
end;
在Prim与Dijkstral中的运用
我们需要做的就是一个找最大（小）值的地方，之后更新。
Prim与Dijkstral的更新大同小异，就是相差了一个Dist而已。
所以就拿Prim的更新来举例。
首先我们找到这个元素在堆中的位置，然后判断是否可以更新，以及调整堆就可以了。
procedure Update(x,w:longint);
var
p:longint;
begin
p:=PIH[x];//在Prim与Dijkstral中，每次找到最大值之后，删除这个节点。已经被删除的节点已经是最优的了。
if p=0 then exit;
if Heap[p].Dist>w then//更新p
begin
Up(p);
Down(p);
end;
end;
当然不仅是Prim与Dijkstral，有一些需要用到堆的地方也要写离散堆。具体视题目而定。