算法优先队列

A. 《漫画算法》—— 【3】树

在树的结构中，树的定义如下。
树（tree）是n（n>=0）个节点的有限集，当n=0时，称为空树。在任意一个非空树中，有如下特点：

1、有且仅有一个特定的称为根的节点。
2、当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

【相关节点】

树的最大层级树，被称为树的高度或深度。

树的每个节点最多有2个孩子节点。
树的一种特殊形式。树的每个节点 最多有2个孩子节点 。

二叉树的两个孩子节点，一个被称为 左孩子 ，一个被称为 右孩子 。这两个孩子节点的顺序是固定的。

二叉树有两种特殊形式：满二叉树、完全二叉树。

满二叉树 ：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层接上。简言之，满二叉树的每一个分支都是满的。

完全二叉树 ：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

一棵树，若为满二叉树，那么一定是完全二叉树。反之，不一定。

在内存中存储 ：

为什么这么设计？可以更方便的定位孩子节点、父节点。
若父节点的下标是parent，那么左孩子节点下标是2 parent+1，右孩子节点下标是2 parent+2。
反之，若左孩子节点下标是leftChild,那么父节点下标是(leftChild - 1)/2。
稀疏二叉树，用数组表示会很浪费空间。

二叉树的应用：查找操作、维持相对顺序。

1、查找

二叉查找树在二叉树的基础上增加了以下几个条件：

如果左子树不为空，则左子树上所有节点的值均小于根节点的值；
如果右子树不为空，则右子树上所有节点的值均大于根节点的值；
左、右子树也都是二叉查找树。

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的 时间复杂度都是O(logn) ，和树的深度是一样的。

2、维持相对顺序（插入）

二叉查找树的特性保证了二叉树的有序性，因此还有另外一个名字：二叉排序树。

插入的过程中，可能会出现需要二叉树进行自平衡，例如下图的情况：

如图所示，不只是树的外观看起来怪异，查询节点的时间复杂度也退化成了O(n)。

二叉树的自平衡的方式有很多种，如红黑树、AVL树、树堆等。

二叉树的遍历：
从节点之间位置关系的角度：
* 前序遍历：输出顺序：根节点、左子树、右子树
* 中序遍历：输出顺序：左子树、根节点、右子树
* 后序遍历：输出顺序：左子树、右子树、根节点
* 层序遍历：按照从根节点到叶子节点的层级关系，一层一层横向遍历各个节点。

从更宏观的角度:
* 深度优先遍历(前、中、后序遍历，前中后是相对根节点)
* 广度优先遍历(层序遍历)

二叉堆：本质上是一种完全二叉树。
二叉堆本质上是一种完全二叉树，分为2个类型：

最大堆 ：任何一个父节点的值，都大于或等于它左、右孩子节点的值；
最小堆 ：任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点，叫作 堆顶 。最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。
二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储，如下图所示：

假设父节点的下标是parent，那么它的左孩子的下标就是 2 * parent + 1 ，右孩子的下标就是 2 * parent + 2 。

二叉堆的3种操作（假设是最小堆）：
1、插入节点：时间复杂度O(logn)
插入节点是通过“上浮”操作完成的：当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，将该节点与它的父节点进行比较，如果该节点小于它的父节点，那么该与它的父节点交换位置，直到比较到堆顶位置。
2、删除节点：时间复杂度O(logn)
删除节点是通过“下沉”操作完成的：将要删除的节点看作是堆顶，只看该节点及它下面的部分。因为堆顶元素要进行删除，将最后一个节点元素替换堆顶元素，将替换后的元素与它的左、右子树进行比较，如果左、右孩子节点中最小的一个比该节点小，那么该节点“下沉”，直到叶子节点。
3、构建二叉堆：时间复杂度O(n)
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点一次“下沉”。

优先队列不再遵循先入先出的原则，而是分为两种情况：

最大优先队列 ，无论入队顺序如何，都是当前最大的元素优先出队；
最小优先队列 ，无论入队顺序如何，都是当前最小的元素优先出队。

二叉堆节点的“上浮”和“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)。

https://blog.csdn.net/qq_28958301/article/details/91590545

B. 已经利用优先队列实现了查找最短路径长度的dijkstra算法，怎么回溯出最短距离路线上经过的点呢

用递归 按你这个代码正轮 就是稿册递归 prev[]数组
不过好像没键清宏看到定义prev? 在全局变量定义一个prev[200] 并全部初始化为-1
void search(int v)
{
if(prev[v]!=-1)
search(prev[v]);
printf(" %d",v);
}

C. 实现优先队列的初始化，查找，插入，删除操作，并且控制其查找，插入，删除操作的算法时间复杂度为O（logn

#include <stdio.h>
#include <stdlib.h>

struct MyHeap
{
int* pnData;
int nSize;
}

int IncreaseKey(MyHeap* pHeap, int nPos)
{
//循环和他父节点判断，只要 nPos > 1他就有父节点
while(nPos > 1)
{
int nMax = pHeap->pnData[nPos];
int nParent = nPos / 2;
if (nMax > pHeap->pnData[nParent])
{
pHeap->pnData[nPos] = pHeap->pnData[nParent];
pHeap->pnData[nParent] = nMax;
nPos = nParent;
}
else
{
break;
}
}

return 1;
}

int Insert(MyHeap* pHeap, int nData)
{
++pHeap->nSize; //添加数据到末尾
pHeap->pnData[pHeap->nSize] = nData;
IncreaseKey(pHeap, pHeap->nSize);
return 1;
}
int PopMaxHeap(MyHeap* pHeap)
{
int nMax = pHeap->pnData[1]; //得到最大元素
int nPos = 1; //起始位1，因为他弹出，所以是这里开始破坏堆得性质的
int nChild = nPos * 2; //他的左孩子的位置，

//循环填充，用最大孩子填充父节点
while(nChild <= pHeap->nSize)
{
int nTemp = pHeap->pnData[nChild];
if (nChild + 1 <= pHeap->nSize &&
nTemp < pHeap->pnData[nChild + 1])
{
++nChild;
nTemp = pHeap->pnData[nChild];
}
pHeap->pnData[nPos] = nTemp;
nPos = nChild;
nChild *= 2;
}
pHeap->pnData[nPos] = pHeap->pnData[pHeap->nSize];
--pHeap->nSize;
return nMax;
}
int main()
{
MyHeap myHeap; //定义一个堆
myHeap.pnData = (int*)::malloc(sizeof(int) *11); //申请数据空间
myHeap.nSize = 0; //初始大小为0

for (int i = 1; i <= 10; ++i) //给优先队列堆里添加数据
{
Insert(&myHeap, i);
}

for (int i = 1; i <= 10; ++i) //测试优先队列是否建立成功
{
printf("%d ", myHeap.pnData[i]);
}
printf("\n");

while(myHeap.nSize > 0) //逐一弹出队列的最大值。并验证
{
printf("%d ", PopMaxHeap(&myHeap));
}
printf("\n");

free(myHeap.pnData);
return 0;
}

D. 五大基本算法——分支限界法

与回溯法一样，分支限界法也是在问题的解空间树上搜索问题的解的一种算法。

两者很类似，很容易混淆，但有如下显着的区别可区分两者：

1、求解目标不同

回溯法的求解目标一般是找出解空间树中满足条件的 所有解 。

分支限界法则是尽快找出满足约束条件的 一个解 ，或是在满足约束条件的解中找出在某种意义下的 最优解 。

2、搜索方式不同

回溯法——> 深度优先 遍历结点搜索解空间树。

分支限界法——> 广度优先或最小耗费优先 搜索解空间树。

3、存储空间不同

分支限界法由于加入了 活结点表 ，所以存储空间比回溯法大得多。因此当内存容量有限时，回溯法的成功率要大一些。

4、扩展结点的方式不同

分支限界法中，每个活结点只有一次机会变成扩展结点，一旦成为扩展结点便一次性生成其所有子结点。

区别小结：回溯法空间效率更高，分支限界法由于只需要求到一个解，所以往往更“快”。

就拿0/1背包问题做例子，回溯法求解0/1背包问题实际上是盲目地搜索解空间树，回溯法只会不断地往下走，虽然通过剪枝函数能减少一定的计算，但是当经过一个结点时，并不知晓其子结点会是怎样的情况，从而盲目继续搜索。而分支限界法则不一样，在经过某一结点时，会根据限界条件判断其结点之下的情况是否能够导出最优解，如若不能，直接不走这条路。这样虽然在空间上不占优势，但是搜索并不盲目，速度上快了很多。

1、定义解空间（对解编码）

2、确定解空间树结构（得解空间树）

3、按BFS广度优先方式搜索解空间树：

（1）：每个活结点只有一次机会变成扩展结点。
（2）：由扩展结点生成一步可达的新结点。
（3）：在新结点中删除不可能导出最优解的结点（限界策略，利用限界函数）。
（4）：将剩余新结点加入到活结点表中。
（5）：在活结点表中再取每个结点（按顺序）进行扩展（分支策略）。
（6）：直到活结点表为空。

注：活结点表通常采用堆结构，当求解极大值问题时用大顶堆，极小值问题时用小顶堆。

1、约束函数：问题定义时需给出的约束条件，如0/1背包问题不能超过其容量。

2、目标函数：是问题要求解的目标函数，分支限界法中需给出一个关于该函数的上下界，方便之后剪枝。

3、限界函数：用于记录当前结点之下可得的最优值，若超出上下界，则可放弃该结点；还用于活结点表中结点排序，限界函数值最优的在第一位，优先扩展遍历。

1、队列式分支限界法：在活结点表中，按照FIFO先进先出原则选取下一个结点做扩展结点。

2、优先队列式分支限界法：活结点表中的每个结点对应了一个耗费或收益（其实就是如果扩展该结点，会带来多大的效益），以此决定结点的优先级。

0/1背包问题、单源最短路径问题、最优装载问题。

E. 优先队列(PriorityQueue)

https://www.jianshu.com/p/94155f9616bf

在数据结构中，普通的队列是先进先出，但有时我们可能并不想有这么固定的规矩，我们希望能有一个带优先级的队列。考虑在现实生活中，一些服务排队窗口会写着“军人依法优先”；送进医院的患者，即便是按顺序到达的，生病更加严重的往往优先级也会更高；还有操作系统中的作业调度也和优扒扰谈先级有关......
于是我们能不能改进队列？使得队列是有一定优先级的，这样能让一些事物和任务的处理变的更加春碰灵活。当然是可以的，最基本的我们可以基于线性结构来实现，考虑基于线性结构的时间复杂度：

1、队列是一种FIFO（First-In-First-Out）先进先出的数据结构，对应于生活中的排队的场景，排在前面的人总是先通过，依次进行。
2、优先队列是特殊的队列，从“优先”一词，可看出有“插队现象”。比如在火车站排队进站时，就会有些比较急的人来插队，他们就在前面先通过验票。优先队列至少含有两种操作的数据结构：insert（插入），即将元素插入到优先队列中（入队）；以及deleteMin（删除最小者），它的作用是找出、删除优先队列中的最小的元素（出队）。

结构\操作 入队 出队
普通线性结构 O(1) O(n)
顺序线性结构 O(n) O(1)
普通线性结构实现的优先队列出队时间复杂度是O(n)，因为出队要拿出最优先的元素，也就是相对最大的元素（注意：大小是相对的，我们可以指定比较规则），从而要扫描一遍整个数组选出最大的取出才行。而对于顺序线性结构的入队操作，入队后可能破坏了原来的有序性，从而要调整当前顺序。
可以看到使用线性结构总有时间复杂度是O(n)的操作，还有没有更好的实现方式呢，当然是有的，这就要来聊一聊堆Heap。

堆严格意义上来说又叫二叉堆（Binary Heap），因为它的结构是一颗完全二叉树，堆一般分为最大堆和最小堆。

堆性质：
结构性：堆是一颗除底层外被完全填满的二叉树，底层的节点从左到右填入，这样的树叫做完全二叉树。即缺失结点的部分一定再树的右下侧。

堆序性：由于我们想很快找出最小元，则最小元应该在根上，任意节点都小于它的后裔，这就是小顶堆（Min-Heap）；如果是查找最大元，则最大元应该在根上，任意节点都要大于它的后裔，这就是大顶堆(Max-heap)。

最大堆：父亲节点的李禅值大于孩子节点的值
最小堆：父亲节点的值小于孩子节点的值

由于是完全二叉树，节点的索引之间有着一定的关系，故我们可以使用数组来存储二叉堆，具体如下：

如果从索引为0开始存储，则父亲和孩子节点的索引关系如下：

当我们需要向一个最大堆添加一条新的数据时，此时我们的堆变成了这样。

此时，由于新数据的加入已经不符合最大堆的定义了。所以我们需要对新加入的数据进行shift up操作，将它放到它应该在的位置。shift up操作时我们将新加入的数据与它的父节点进行比较。如果比它的父节点大，则交换二者。

此时我们就完成了 对新加入元素的shift up操作。

当我们从堆中(也就是优先队列中)取出一个元素时。我们是将堆顶的元素弹出。(只能从堆顶取出)

此时这个堆没有顶了，那么该怎么办呢？我们只需要把这个堆最后一个元素放到堆顶就可以了。

此时我们就完成了弹出一个元素之后的shift down操作。

replace:去除最大元素后，放入一个新元素
实现：可以先extractMax,再add，两次longn操作。
实现:将堆顶的元素替换以后sift down，一次O(logn)操作

将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn),heapify的过程，算法的复杂度为O(n).

heapify:将任意数组整理成堆的形状。
首先将一个数组抽象成一个堆。这个过程，我们称之为heapify。

之后我们找到这个堆中第一个非叶子节点，这个节点的位置始终是数组的数量除以2，也就是索引5位置的27，从这个节点开始，对每一个非叶子的节点,，进行shift down操作。
27比它的子节点51要小，所以交换二者。

接下来我们看索引2位置的20。首先呢，我们需要将20与它两个子节点中较大的51交换。

每个节点堆化的时间复杂度是O(logn)，那 个节点的堆化的总时间复杂度是O(nlogn)。
推导过程
堆化节点从倒数第二层开始。堆化过程中，需要比较和交换的节点个数与这个节点的高度k成正比。

所以 heapify() 时间复杂度是 O(n).
建堆后，数组中的数据是大顶堆。把堆顶元素，即最大元素，跟最后一个元素交换，那最大元素就放到了下标为n的位置。
这个过程有点类似上面的“删除堆顶元素”的操作，当堆顶元素移除之后，把下标n的元素放堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。一直重复这个过程，直到最后堆中只剩下下标为1的元素，排序就完成了。

topk和selectk问题既可以使用快排思想解决，也可以使用优先队列解决。
快排:O(n) 空间O(1)
优先队列:O(nlogk) 空间O(k)
优先队列的有i是，不需要一次性知道所有数据,数据流的方式处理。

F. 优先队列实现dijkstra算法C++代码

#include<fstream>
#define MaxNum 765432100
using namespace std;
ifstream fin("Dijkstra.in");
ofstream fout("Dijkstra.out");
int Map[501][501];
bool is_arrived[501];
int Dist[501],From[501],Stack[501];
int p,q,k,Path,Source,Vertex,Temp,SetCard;
int FindMin()
{
int p,Temp=0,Minm=MaxNum;
for(p=1;p<=Vertex;p++)
if ((Dist[p]<Minm)&&(!is_arrived[p]))
{
Minm=Dist[p];
Temp=p;
}
return Temp;
}
int main()
{
memset(is_arrived,0,sizeof(is_arrived));
fin >> Source >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
if (Map[p][q]==0) Map[p][q]=MaxNum;
}
for(p=1;p<=Vertex;p++)
{
Dist[p]=Map[Source][p];
if (Dist[p]!=MaxNum)
From[p]=Source;
else
From[p]=p;
}
is_arrived[Source]=true;
SetCard=1;
do
{
Temp=FindMin();
if (Temp!=0)
{
SetCard=SetCard+1;
is_arrived[Temp]=true;
for(p=1;p<=Vertex;p++)
if ((Dist[p]>Dist[Temp]+Map[Temp][p])&&(!is_arrived[p]))
{
Dist[p]=Dist[Temp]+Map[Temp][p];
From[p]=Temp;
}
}
else
break;
}
while (SetCard!=Vertex);
for(p=1;p<=Vertex;p++)
if(p!=Source)
{
fout << "========================\n";
fout << "Source:" << Source << "\nTarget:" << p << '\n';
if (Dist[p]==MaxNum)
{
fout << "Distance:" << "Infinity\n";
fout << "Path:No Way!";
}
else
{
fout << "Distance:" << Dist[p] << '\n';
k=1;
Path=p;
while (From[Path]!=Path)
{
Stack[k]=Path;
Path=From[Path];
k=k+1;
}
fout << "Path:" << Source;
for(q=k-1;q>=1;q--)
fout << "-->" << Stack[q];
}
fout << "\n========================\n\n";
}
fin.close();
fout.close();
return 0;
}
Sample Input
2
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 00
00 70 50 00 10 00 00
00 00 00 00 00 00 00
Sample Output
========================
Source:2
Target:1
Distance:20
Path:2-->1
========================
========================
Source:2
Target:3
Distance:25
Path:2-->3
========================
========================
Source:2
Target:4
Distance:50
Path:2-->1-->4
========================
========================
Source:2
Target:5
Distance:50
Path:2-->3-->5
========================
========================
Source:2
Target:6
Distance:60
Path:2-->3-->5-->6
========================
========================
Source:2
Target:7
Distance:Infinity
Path:No Way!
========================
示例程序及相关子程序：
void Dijkstra(int n,int[] Distance,int[] iPath)
{
int MinDis,u;
int i,j;
//从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance[]
for(i=0;i<VerNum;i++)
{
Distance=Arc[n,i];
Visited=0;
}//第n个顶点被访问，因为第n个顶点是开始点
Visited[n]=1;
//找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。
//相当于寻找u点，这个点不是开始点n
for(i=0;i<VerNum;i++)
{
u=0;
MinDis=No;
for(j=0;j<VerNum;j++)
if(Visited[j] == 0&&(Distance[j]<MinDis))
{
MinDis=Distance[j];
u=j;
}
//如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2
//找完了，MinDis等于不连接，则返回。这种情况类似V5。
if(MinDis==No) return ;
//确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。
Visited[u]=1;
//寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，VerNum]。
//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，则Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]
//实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是：
//如果(Distance[u] + Arc[u,j]) <= Distance[j] 则：
//Distance[j] = Distance[u] + Arc[u, j]；
//而iPath[]保存了u点的编号；
//同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3
for(j=0;j<VerNum;j++)
if(Visited[j]==0&&Arc[u,j]<No&&u!= j)
{
if ((Distance[u] + Arc[u,j]) <= Distance[j])
{
Distance[j] = Distance[u] + Arc[u, j];
Visited[j]=0;
iPath[j] = u;
}
}
}
}
//辅助函数
void Prim()
{
int i,m,n=0;
for(i=0;i<VerNum;i++)
{
Visited=0;
T=new TreeNode();
T.Text =V;
}
Visited[n]++;
listBox1.Items.Add (V[n]);
while(Visit()>0)
{
if((m=MinAdjNode(n))!=-1)
{
T[n].Nodes.Add(T[m]);
n=m;
Visited[n]++;
}
else
{
n=MinNode(0);
if(n>0) T[Min2].Nodes.Add(T[Min1]);
Visited[n]++;
}
listBox1.Items.Add (V[n]);
}
treeView1.Nodes.Add(T[0]);
}
void TopoSort()
{
int i,n;
listBox1.Items.Clear();
Stack S=new Stack();
for(i=0;i<VerNum;i++)
Visited=0;
for(i=VerNum-1;i>=0;i--)
if(InDegree(i)==0)
{
S.Push(i);
Visited++;
}
while(S.Count!=0)
{
n=(int )S.Pop();
listBox1.Items.Add (V[n]);
ClearLink(n);
for(i=VerNum-1;i>=0;i--)
if(Visited==0&&InDegree(i)==0)
{
S.Push(i);
Visited++;
}
}
}
void AOETrave(int n,TreeNode TR,int w)
{
int i,w0;
if(OutDegree(n)==0) return;
for(i=0;i<VerNum;i++)
if((w0=Arc[n,i])!=0)
{
listBox1.Items.Add (V+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString());
TreeNode T1=new TreeNode();
T1.Text =V+" [W="+(w+w0).ToString()+"]";
TR.Nodes.Add(T1);
AOETrave(i,T1,w+w0);
}
}
void AOE()
{
int i,w=0,m=1;
TreeNode T1=new TreeNode();
for(i=0;i<VerNum;i++)
{
Visited=0;
}
T1.Text =V[0];
listBox1.Items.Add ("双亲表示法显示这个生成树：");
listBox1.Items.Add ("V\tW\tID\tPID");
for(i=0;i<VerNum;i++)
{
if((w=Arc[0,i])!=0)
{
listBox1.Items.Add (V+"\t"+w.ToString()+"\t"+i.ToString()+"\t0");
TreeNode T2=new TreeNode();
T2.Text=V+" [W="+w.ToString()+"]";
AOETrave(i,T2,w);
T1.Nodes.Add (T2);
listBox1.Items.Add("\t\t树"+m.ToString());
m++;
}
}
treeView1.Nodes.Clear();
treeView1.Nodes.Add (T1);
}
int IsZero()
{
int i;
for(i=0;i<VerNum;i++)
if(LineIsZero(i)>=0) return i;
return -1;
}
int LineIsZero(int n)
{
int i;
for(i=0;i<VerNum;i++)
if (Arc[n,i]!=0) return i;
return -1;
}
void DepthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
Visited=0;
T=new TreeNode();
T.Text =V;
R=0;
}
while((m=IsZero())>=0)
{
if(Visited[m]==0)
{
listBox1.Items.Add (V[m]);
R[m]=1;
}
Visited[m]++;
DTrave(m);
}
for(i=0;i<VerNum;i++)
{
if(R==1)
treeView1.Nodes.Add (T);
}
}
void DTrave(int n)
{
int i;
if (LineIsZero(n)<0) return;
for(i=VerNum-1;i>=0;i--)
if(Arc[n,i]!=0)
{
Arc[n,i]=0;
Arc[i,n]=0;
if(Visited==0)
{
listBox1.Items.Add (V);
T[n].Nodes.Add (T);
R=0;
}
Visited++;
DTrave(i);
}
}
void BreadthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
Visited=0;
T=new TreeNode();
T.Text =V;
R=0;
}
while((m=IsZero())>=0)
{
if(Visited[m]==0)
{
listBox1.Items.Add (V[m]);
R[m]=1;
}
Visited[m]++;
BTrave(m);
}
for(i=0;i<VerNum;i++)
{
if(R==1)
treeView1.Nodes.Add (T);
}
}
void BTrave(int n)
{
int i;
Queue Q=new Queue();
Q.Enqueue(n);
while(Q.Count!=0)
{
for(i=0;i<VerNum;i++)
{
if(Arc[n,i]!=0)
{
Arc[n,i]=0;
Arc[i,n]=0;
if(Visited==0)
{
listBox1.Items.Add(V);
T[n].Nodes.Add (T);
R=0;
}
Visited++;
Q.Enqueue(i);
}
}
n=(int )Q.Dequeue();
}
}
int MinNode(int vn)
{
int i,j,n,m,Min=No;
n=-1;m=-1;
for (i=vn;i<VerNum;i++)
for(j=0;j<VerNum;j++)
if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited==0&&Visited[j]==1)
{
Min=Arc[i,j];n=i;m=j;
}
Min1=n;Min2=m;
return n;
}
int MinAdjNode(int n)
{
int i,Min,m;
Min=No;m=-1;
for(i=0;i<VerNum;i++)
if(Arc[n,i]!=No&&Visited==0&&Min>Arc[n,i]&&Visited[n]==1)
{
Min=Arc[n,i];m=i;
}
return m;
}
int Visit()
{
int i,s=0;
for(i=0;i<VerNum;i++)
if(Visited==0) s++;
return s;
}

[编辑本段]dijkstra算法的Pascal实现：
program dijkstra;
var
a:array[1..100,1..100]of integer;
flag:array[1..100]of boolean;
w,x,n,i,j,min,minn:integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
fillchar(flag,sizeof(flag),false);
flag[1]:=true;
minn:=1;
for x:=2 to n do
begin
min:=32767;
for i:=2 to n do
if (a[1,i]<min)and(flag=false) then
begin
min:=a[1,i];
minn:=i;
end;
flag[minn]:=true;
for j:=1 to n do
if (j<>minn) and (a[1,minn]+a[minn,j]<a[1,j]) and(flag[j]=false) then
a[1,j]:=a[1,minn]+a[minn,j];
end;
for i:=1 to n do
write(a[1,i],' ');
end.
4
0 100 30 999
100 0 99 10
30 99 0 99
999 10 99 0
程序输出：0 100 30 110
dijkstra算法的MATLAB实现：
clear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';
pb(1:length(a))=0;pb(i)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=M;d(i)=0;temp=1;
while sum(pb)<length(a)
tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb));
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(i));
pb(temp)=1;
index1=[index1,temp];
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index;
end
d, index1, index2
matlab编程
function [s,d]=minroute(i,m,w,opt)
% 图与网络论中求最短路径的dijkstra算法M函数
% 格式[s,d]=minroute(i,m,w,opt)
if nargin<4,opt=0;end
dd=[];tt=[];ss=[];ss(1,1)=i;v=1:m;v(i)=[];
dd=[0;i];kk=2;[mdd,ndd]=size(dd);
while~isempty(v)
[tmpd,j]=min(w(i,v));tmpj=v(j);
for k=2:ndd
[tmp2,jj]=min(dd(1,k)+w(dd(2,k),v));
tmp2=v(jj);tt(k-1,:)=[tmp1,tmp2,jj];
end;
tmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(;,1));
if tmp3==tmpd
ss(1:2,kk)=[i;tmp(tmp4,2)];
else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);
if dd(2,tmp4)=ss(tmp6,tmp4)
ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];
else,ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];
end;end
dd=[dd,[tmp3,tmp(tmp4,2)]];v(tmp(tmp4,3))=[];
[mdd,ndd]=size(dd);kk=kk+1;
end;
if opt==1
[tmp,t]=sort(dd(2,:));s=ss(:t);d=dd(1,t);
else,s=ss;d=dd(1,:);
end

G. 双端优先队列是什么，希望高人详细解释一下。

双端优先队列是一个支持如下操作的数据结构：

Insert（S, x)x插入集合S
Extract-Min(S)删除最小关键字
Extract-Max(S)删除最大关键字
用小大根交替堆实现上述操作。小大根交替堆是满足如下条件的完全二元树：如树不空，那么其上每个元素有一称为关键字的域，且针对该关键字二元树按层次形成了小大根交替的形式，即对于任何一结点x，如x位于小根层次，那么x是以x为根节点的二元树中键值最小的结点，称该结点为一个小根结点。如果x位于大根层次，那么x是以x为根节点的最大结点，称该结点为一大根结点。交替堆中根结点位于小根层次。
假设要在上图的堆中插入键值为5的元素。小大根交替堆上的插入算法也要针对从新插入结点到根结点的路径进滑芦行处理。需要比较键值5和父结点键值（10）的大小关系，由于10位于小根层次且5<10，就决定5定比从新加结点到根结点路径上的所有大根结点都要小，即5无论放在那里都不影响大根层次的性质，插入5时需调整从新加结点到根结点路径上的小根结点就使整个堆凳让纤满足性质。调整过程：5<10，所以10下移填新结点；接着，5和7比较，5<7，所以7填到原来10的位置；最后将5填入根结点。
考虑在上图中插入键值80的元素。10仍处于小根，80>10，有80大于从新加结点到根结点路径上的所有小根结点，决定插入80时只需调整从新加结点到根结点路径上的大根就能使整个堆满足性质。只有一满足条件的结点——键值40的结点。80>40，40将下移填入新加结点，80将填入原40结点所占位置。
如我们要删除堆中键值最小的元素，那么删除的是根结点，对于上图，就是7。删除7以后，堆中就剩下11个元素，拟用最后一个元素（键值12）重填。和普通的小根堆类似，重填将引起从根到叶的检查。
考虑实现元素item对根结点的重填，需分析两种情况：
如根没有儿子结点。
item直接填入根结点即可。
如根至少存在一个儿子结点。堆中键值最小的结点定出现在根结点儿子或孙子中，可以容易找到，标记为k。再分成几种进行考虑：
item.key <= heap[k].key。
item直接插入根结点，因为item是最小的结点。
item.key > heap[k].key 且 k 是根的儿子。
由于k是大根，所以其后代中不可能有大于heap[k].key的结点，就没有键值大于item.key的。此时将heap[k]移到根结点，后将item插入k所在位置。
item.key > heap[k].key 且 k 是根结点孙子。
此种情况也是先将heap[k]移到根，将item插入k所在位置。考察k的父结点，如item.key>heap[parent].key，就将heap[parent]和item互换，保证了parent处的键值是以parent为根的子堆中最大的，即parent满足大根条件。此时需考虑如何将item插入到以k为根的子堆中，现在该子堆的根为空，显然此时情况和初始情况相似，可以重复上述处理。
本例有item.key=12，且根结点的所有儿子和孙子中最小值为9，9所对应结点用k标记，其父结点用p标记。由于9<12且k是根的孙子 。所以9对应的元素将移到根处，又条件item.key=12<70=h[p].key，不需要交换x和h[p]。现需枣仿将item插入到以k为根的子堆中，k的所有儿子和孙子结点中最小值为20，2<20 ，将item插入h[k]中即可。

H. 优先队列和堆排序的区别是什么

简单来说：堆排序是一种排序算法，利用堆结构完成排序的功能；优先队列是一种数据结构，它是利用堆来实现。
具体来说，堆排序过程：建堆→堆顶就是最大(或小)值，然后堆顶跟最后一个元素交换→调整堆，反复这个过程，直到堆里面所有元素都交换好；
而优先队列：建堆→堆顶元素就是优先级最高（或最低）的元素了，可以利用优先级这个数据结构来描述某个问题，比如有一批不断输入胡余的日期，我毕做察想要在任何时刻都能以O(1)的速度得到已经输入的日期中的最早日期，那么就可以用优先队列这个数据结构存储手茄日期元素啦。

I. C语言实现优先队列(priority queue)

        堆排序是一个比较优秀的算法,堆这种数据结构在现实生活中有很多的应用,比如堆可以作为一个优先队列来使用,作为一个高效的优先队列,它与堆的结构一样,都有最大优先队列,最小优先队列.优先队列priority queue 是一种用来维护一组元素构成的集合S的数据结构，每一个元素都有一个相关的值，称为关键字（key）。

        最大优先队列包含以下操作：

         将元素x插入到S的集合中，等价于 ；

         返回S中最大元素；

         返回并且删除S中最大元含李素；

         将元素x的关键字增加到key，要求 。

        同样的，最小优先队列操作也包括： , , , 。只不过是对最小值进行操作。

        在这里主要讨论最大优先队列，其应用很多，在共享计算机作业系统就是，类似于早期的unix主机，管理员root可以设置n个不同的用户，以及各个用户不同的操作权限，从主机那里接出多个终端，每个操作人员（程序员）在自己的工作终端 ，感觉像是自己拥有自己独立的作业主机一样，其实不是，通过一些任务调度来实现，其中就有任务等待执行相关队列，并且有各个任务有着自己优先级，以便确定调度执行具体任务，如果你学过操作系统相关知识，那么应该对系统调度有所了解。

        当一个作业被完成或者被中断后，调度器会调用 来调用所有在队列中等待任务中优先级最高的任务执行，在新任务加入等待任务时会配稿调用 加入任务等待队列，当某个任务等待时间过长时可通过 提高其优先级培老孝，从而减少等待时间。

        下面是具体实现C程序源码：

#include <stdio.h>

#define NAGE_INFINIT -99999

#define parent(i) i/2

#define left(i) 2*i+1

#define right(i) 2*i+2

//get array of A first element

int heap_maximum(int A[]){ return A[0];}

/***********************************************

*

* function max_heapify();

*

* args

*  A[] inttype save elements of heap

*  i index of A

*  heap_size real length of A

*

* ********************************************/

void max_heapify(int A[],int i,int heap_size){

    int l,r,largest,temp;

    l=left(i);

    r=right(i);

    if((l<=heap_size)&&(A[l]>A[i]))

        largest=l;

    else

        largest=i;

    if((r<=heap_size)&&(A[r]>A[largest]))

        largest=r;

    if(largest!=i){

        temp=A[i];

        A[i]=A[largest];

        A[largest]=temp;

        max_heapify(A,largest,heap_size);

    }

}

/*********************************************

*

* function heap_extract_max()

*

* args

*  A[] inttype save elements of heap

*  heap_size inttype the real length of A

*

* return max the parent node value

*

* ******************************************/

int heap_extract_max(int A[],int heap_size){

    int max;

    if(heap_size<0)

        return -1;  //heap underflow

    max=A[0];  //parent node the max value of element

    A[0]=A[heap_size];

    heap_size--;

    /**************************************

    * dajust binary heap(or tree) to make

    * sure heap fo A true every times

    *

    * ************************************/

    max_heapify(A,0,heap_size);

    return max;

}

/***********************************************

*

* function heap_increase_key();

*

* args

*  A[] inttype save elemnts of heap

*  i index of A

*  key inserted element

*

* *********************************************/

void heap_increase_key(int A[],int i,int key){

    int temp;

    if(key<A[i]){

        printf("new key is smaller than current key\n");

        return;    //over programming

    }

    A[i]=key;

    //p=parent(i);

    while ((i>0)&&(A[parent(i)]<A[i])) {

        temp=A[i];

        A[i]=A[parent(i)];

        A[parent(i)]=temp;

        i=parent(i); //update index of A

        //p=parent(i);

    }

}

/***************************************************

*

* function max_heap_insert();

*

* args

*  A[] inttype save elements of A

*  key inserted element to A

*  heap_size real length of A

*

* **************************************************/

void max_heap_insert(int A[],int key,int heap_size){

    heap_size+=1;

    A[heap_size]=NAGE_INFINIT;

    heap_increase_key(A,heap_size,key);

}

int main()

{

    int heap_max,max,i,key;

    int A[11],Temp[11];

    int heap_size=0;

    char c;

    while (1) {

        scanf("%d",&A[heap_size]);

        c=getchar();

        if(c=='\n')

            break;

        heap_size++;

    }

    // A to Temp

    for(i=0;i<=heap_size;i++)

        Temp[i]=A[i];

    //get heap maximum element

    heap_max=heap_maximum(A);

    printf("heap of A maximum element: %d\n",heap_max);

    // Temp to A

    for(i=0;i<=heap_size;i++)

        A[i]=Temp[i];

    /*--extract maximum element--*/

    max=heap_extract_max(A,heap_size);

    printf("extract element: %d \n",max);

    printf("new heap of A after extract maximum node\n");

    for(i=0;i<heap_size;i++)

        printf("%d ",A[i]);

    printf("\n");  //next line

    // Temp to A

    for(i=0;i<=heap_size;i++)

        A[i]=Temp[i];

    /*--increase from A[i] to key--*/

    printf("input i key ");

    scanf("%d %d",&i,&key);

    heap_increase_key(A,i,key);

    for(i=0;i<=heap_size;i++)

        printf("%d ",A[i]);

    printf("\n");

    // Temp to A

    for(i=0;i<=heap_size;i++)

        A[i]=Temp[i];

    /*--insert queueu--*/

    key=0;  //init key;

    printf("input key: ");

    scanf("%d",&key);

    max_heap_insert(A,key,heap_size);

    for(i=0;i<=heap_size+1;i++)

        printf("%d ",A[i]);

    printf("\n");

    return 0;

}

/****************************************

*

* input 16 14 10 8 7 9 3 2 4 1

*      i: 8

*      key: 15

*

* output in function main()

* **************************************/

其运行结果如下图：

欢迎留言交流，也感谢指正，一起进步。

J. 看图说话之二叉堆(优先队列)——原理解析

    优先队列更多的是一种逻辑上和业务上的设计。队列中的每项元素都分配一个优先权值，队列的出队顺序按照优先权值来划分，高优先权先出队或者低优先权先出队。这样一个优先队列必须具备两个最基本的操作——入队，以及高(低)优先权出队。优先队列在很多场景中都有运用，比如打印机的任燃答段务调度和操作系统中的进程调度都有用到优先队列的设计。

    此时我们假设并不知道有堆这样的数据结构，想实现上述这样的功能，其实也可以有多种解决方案，比如以下两种：

    二叉堆如其名字一样和二叉树具有紧密的关系。二叉堆是一种特殊的二叉树，是对一般的二叉树提出了结构性和堆序性的要求，这种特殊结构性和堆序性是二叉堆的性质所在。

1.结构性：二叉堆是一个完全二叉树

2.堆序性：所有的节点值均小于(大于)其后裔节点值，若所有节点值大于其后裔节点这样的二叉堆称为大根堆##点值均小于其后裔节点这样的二叉堆成为小根堆。

    这里可以看到，假如是小根堆的情况，那么每次取堆顶的元素，就完成了按低优先级出队的功能。若是大根队取堆顶的元素则完成按高优举嫌先级出对的顺序。
    这里需要特别注意就是，每次的出队操作=返回堆顶元素+删除堆顶元素，每次删除堆顶元素之后，需要保证依旧满足二叉堆的结构性和对堆序性，这个删除和调整的过程称为堆调整。
    下面以大根堆为例进行介绍一次堆调整，并且分析其时间复杂度为什么是O(logN)。下文描述中，堆的删除操作=优先队列的出队，堆的插入操作=优先队列的入队。

    上文介绍了大根堆的出队操作，其时间复杂度在O(logN),此处介绍大根堆的入队操作，入队操作和出队操作和其相似，最坏时间复杂度也是O(logN)。下面将通过图例的形式分析大根堆的入队操作，假设插入元素是19。

2.如图9所示，皮誉在插入元素之后二叉堆的结构特性已经满足了，下面主要需要调整堆序特性。对于元素19而言，找到其父亲元素8，判断堆序性，发现19大于8，所以交换19和8的位置，结果如下。

Reference:
[1] 数据结构与算法 java语言描述版
[2] 博客原文