演算法優先隊列

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] 博客原文