堆（heap），是一類特殊的資料結構的統稱。它通常被看作一棵樹的數組對象。在隊列中，排程程式反複提取隊列中的第一個作業并運作，因為實際情況中某些時間較短的任務卻可能需要等待很長時間才能開始執行，或者某些不短小、但很重要的作業，同樣應當擁有優先權。而堆就是為了解決此類問題而設計的資料結構。
二叉堆是一種特殊的堆，二叉堆是完全二叉樹或者近似完全二叉樹，二叉堆滿足堆特性：父節點的鍵值總是保持固定的序關系于任何一個子節點的鍵值，且每個節點的左子樹和右子樹都是一個二叉堆。
當父節點的鍵值總是大于任何一個子節點的鍵值時為最大堆，當父節點的鍵值總是小于或等于任何一個子節點的鍵值時為最小堆。
為了更加形象，我們常用帶數字的圓圈和線條來表示二叉堆等，但其實都是用數組來表示的。如果根節點在數組中的位置是1，第n個位置的子節點則分别在2n和2n+1位置上。
如下圖所描的，第2個位置的子節點在4和5，第4個位置的子節點在8和9。是以我們獲得父節點和子節點的方式如下：
假定表示堆的數組為a，那麼a.length通常給出數組元素的個數，a.heap−size表示有多少個堆元素存儲在該數組中。這句話略帶拗口，也就是說數組a[1...a.length]可能都有資料存放，但隻有a[1...a.heap−size]中存放的資料才是堆中的有效資料。毫無疑問0≤a.heap−size≤a.length。
最大堆除了根以外所有結點i都滿足：a[parent(i)]≥a[i] 。
最小堆除了根以外所有結點i都滿足：a[parent(i)]≤a[i] 。
一個堆中結點的高度是該結點到葉借點最長簡單路徑上邊的數目，如上圖所示編号為4的結點的高度為1，編号為2的結點的高度為2，樹的高度就是3。
包含n個元素的隊可以看作一顆完全二叉樹，那麼該堆的高度是Θ(lgn)。
程式中，不可能所有的堆都天生就是最大堆，為了更好的使用堆這一資料結構，我們可能要人為地構造最大堆。
如何将一個雜亂排序的堆重新構造成最大堆，它的主要思路是：
從上往下，将父節點與子節點以此比較。如果父節點最大則進行下一步循環，如果子節點更大，則将子節點與父節點位置互換，并進行下一步循環。注意父節點要與兩個子節點都進行比較。
如上圖說描述的，這裡從結點為2開始做運算。先去l為4，r為5，将其與父節點做比較，發現左子節點比父節點更大。是以将它們做交換，設4為最大的結點，并繼續以結點4開始做下一步運算。
是以可以給出僞代碼如下：
在以上這些步驟中，調整a[i]、a[l]、a[r]的關系的時間代價為Θ(1)，再加上一棵以i的子節點為根結點的子樹上運作max-heapify的時間代價（注意此處的遞歸不一定會發生，此處隻是假設其發生）。因為每個子節點的子樹的大小至多為2n/3（最壞情況發生在樹的底層恰好半滿的時候）。是以max-heapify過程的運作時間為：
t(n)≤t(2n/3)+Θ(1)
也就是：
t(n)=o(lgn)
前面我們通過自頂向下的方式維護了一個最大堆，這裡将通過自底向上的方式通過max-heapify将一個n=a.length的數組a[1...n]轉換成最大堆。
回顧一下上面的圖示，其總共有9個結點，取小于或等于9/2的最大整數為4，從4+1，4+2，一直到n都是該樹的葉子結點，你發現了麼？這對任意n都是成立的哦。
是以這裡我們就要從4開始不斷的調用max-heapify(a,i)來建構最大堆。
為什麼會有這一思路呢？
原因是既然我們知道了哪些結點是葉子結點，從最後一個非葉子結點（這裡是4）開始，一次調用max-heapify函數，就會将該結點與葉子結點做相應的調整，這其實也就是一個遞歸的過程。
圖示已經這麼清晰了，就直接上僞代碼咯。
所謂的堆排序算法，先通過前面的build-max-heap将輸入數組a[1...n]建成最大堆，其中n=a.length。而數組中的元素總在根結點a[1]中，通過把它與a[n]進行互換，就能将該元素放到正确的位置。
如何讓原來根的子結點仍然是最大堆呢，可以通過從堆中去掉結點n，而這可以通過減少a.heap−size來間接的完成。但這樣一來新的根節點就違背了最大堆的性質，是以仍然需要調用max-heapify(a,1)，進而在a[1...n−1]上構造一個新的最大堆。
通過不斷重複這一過程，知道堆的大小從n−1一直降到2即可。
上圖的演進方式主要有兩點：
1）将a[1]和a[i]互換，i從a.length一直遞減到2
2）不斷調用max-heapify(a,1)對剩餘的整個堆進行重新建構
一直到最後堆已經不存在了。
下一篇博文我們就會介紹大名鼎鼎的快排，快速排序啦，歡迎童鞋們預定哦~
話說堆排序雖然性能上不及快速排序，但作為一個盡心盡力的資料結構而言，其可謂業界良心呐。它還為我們提供了傳說中的“優先隊列”。
優先隊列（priority queue）和堆一樣，堆有最大堆和最小堆，優先隊列也有最大優先隊列和最小優先隊列。
優先隊列是一種用來維護由一組元素構成的集合s的資料結構，其中每個元素都有一個相關的值，稱之為關鍵字（key）。
一個最大優先隊列支援一下操作：
maximum(s)：傳回s中有着最大鍵值的元素。
extract−max(s)：去掉并傳回s中的具有最大鍵字的元素。
increase−key(s,x,a)：将元素x的關鍵字值增加到a，這裡假設a的值不小于x的原關鍵字值。
insert(s,x)：将元素x插入集合s中，這一操作等價于s=s∪{x}。
這裡來舉一個最大優先隊列的示例，我曾在關于“50% cpu 占有率”題目的内容擴充 這篇博文中簡單介紹過windows的系統程序機制。
這裡以圖檔的形式簡單的貼出來如下：
在用堆實作優先隊列時，需要在堆中的每個元素裡存儲對應對象的句柄（handle）。句柄的準确含義依賴于具體的應用程式，可以是指針，也可以是整型數。
在堆的操作過程中，元素會改變其在數組中的位置，是以在具體實作中，在重新确定堆元素位置時，就自然而然地需要改變其在數組中的位置。
一、前面的maximum(s)過程其實很簡單，完全可以在Θ(1)時間内完成，因為隻需要傳回數組的第一個元素就可以呀，它已經是最大優先隊列了嘛。
二、extract−max(s)就稍顯複雜了一點，它的時間複雜度是o(lgn)，因為這裡面除了max-heapify(a,1)以外，其他的操作都是常量時間的。
三、increase−key(s,x,a)需要将一個大于元素x原有關鍵字值的a加到元素x上。
和上一個函數一樣，首先判斷a知否比原有的關鍵字更大。
然後就是老辦法了，不斷的将該結點與父結點做對比，如果父結點更小，那麼就将他們進行對換。
相信有圖示會更加清楚，于是……再來一張圖。
在包含n個元素的堆上，heap-increase-key的運作時間就是o(lgn)了。因為在第3行做了關鍵字更新的結點到根結點的路徑長度為o(lgn)。
四、insert(s,x)首先通過一個特殊的關鍵字（比如這裡的-10000擴充）結點來擴充最大堆，然後調用heap-increase-key來為新的結點設定對應的關鍵字，同時保持最大堆的性質。
在包含n個元素的堆上，max-heap-insert的運作時間就是o(lgn)了。因為這個算法相對于上一個算法，除了heap-increase-key之外就都是常量的運作時間了，而heap-increase-key的運作時間我們在上一部分已經講過了。
總而言之，在一個包含n個元素的堆中，所有優先隊列的操作時間都不會大于o(lgn)。
學過沒學過算法的應該都聽過棧和隊列了吧，往往容易弄混的就是“後進先出”和“先進先出”了。
今天又看到了“河内塔”的相關資料，也被稱為“漢諾塔”等。于是就想到了畫出下面這樣的圖案。
如果大家覺得這張圖不錯可以直接右鍵另存為哦，記得點贊哈~
那麼，關于棧和隊列下面就直接列出相關操作的僞代碼咯。
棧
隊列
原諒我拙劣的繪圖能力，花了半天終于還是決定從網上找來了這三張圖，因為環形連結清單的弧形箭頭難以完美的展現出來。
以下3張圖檔來自wikipedia。
大家看着圖檔應該也都知道這分别是哪種連結清單了。那麼連結清單到底是什麼呢？
它和前面的棧和隊列一般，都是基本的資料結構，其中的各個對象按線性順序排列。大家應該注意到了圖中的大黑點，有些c/c++程式設計基礎的同學肯定能夠猜到連結清單是通過各個對象裡的指針來指向下一個對象的，相比，數組則是通過下标來進行索引。
為了讓大家加深印象，我們來聯系到生活中的執行個體。
首先是單向連結清單（singly linked），我第一個聯想到的就是下面這種鉛筆，滿滿的兒時回憶呀！找了好久才找到這張圖，卻不知道它的名字。
然後是雙向連結清單（doublely linked list），動車組則可以很好的诠釋它。
循環連結清單（circular linked list）的應用是比較多的，從小接觸的自行車鍊條就是其中之一。
大家要是還有什麼例子歡迎在評論中留下哦。
單連結清單
前面已經說到了，連結清單通過指針來指向下一個對象。單連結清單中有一個關鍵字key和指針next，當然了，對象中還可以有其他的衛星資料。我們可以這樣想象它，前面的圖中是一行對吧，然後在行中的連結清單節點中向下延伸，每個節點都延伸成一列，簡單的說，從一維變成了二維（類比二維數組）。
将連結清單中的一個元素設為x，那麼x.key就是它的值，x.next就是連結清單中的後繼元素。如果x.next=nil，那麼就說明沒有後繼元素了，是以x就是連結清單的尾（tail）。
雙向連結清單
将單連結清單更新到雙向連結清單來考慮，無非就是多了一個前驅，用x.prev來表示。同樣的，x.prev=nil，表示沒有前驅，那麼x就是連結清單的頭（head）。而如果頭都為空了，那麼整個連結清單也就是空的了。
循環連結清單
相應的，循環連結清單也由雙向連結清單更新而來，就是将連結清單尾部的元素x的next指向連結清單的頭部y，元素頭部的元素y的prev指向連結清單的尾部x。
搜尋
我們的目的是要搜尋對外連結表l中第一個關鍵字為k的元素，函數傳回的将是指向該元素的指針。
如果不幸的是連結清單中不存在這個元素，那麼就傳回nil。
由于這個搜尋是線性的，在最壞的情況下它會搜尋整個連結清單，是以該情況下list-search的運作時間為Θ(n)。
循環
接下來我們将元素x（已經設定好關鍵字key）插入到連結清單中，這個相比搜尋就有些複雜，因為它要修改的東西較多一些。l.head.prev的意思是去連結清單的頭節點元素，然後取它的prev屬性。
它僅僅是在開頭插入一個元素而已，是以耗時僅僅是Θ(1)。
删除
我們有了一個指向x的指針，然後要将x從清單中删除掉。具體的思路也非常的簡單，例如有依次連結的a、b、c三個節點，如果要将b删除掉，隻需要将a的next指向c即可，如果是雙線連結清單也請記得将c的prev指向a。
由于這裡的x已經是指針了，是以删除操作隻需要Θ(1)的時間，而如果給定的不是指針而是關鍵字，那麼就要調用list-search先搜尋到指針x，這樣的話時間就是Θ(n)。
今天我忽然覺得在部落格上多加點圖檔，即便是現在這個“哨兵”圖像，雖然和連結清單沒太大關系，但也許可以幫助記憶呢，因為記憶真的非常非常重要。
廢話不多說，哨兵是什麼呢，能夠做什麼呢？
哨兵節點常常被用在連結清單和周遊樹中，它并不擁有或引用任何被資料結構管理的資料。常常用哨兵節點來代替null，這樣的好處有以下3點：
1）增加操作的速度
2）降低算法的複雜性和代碼的大小
3）增加資料結構的魯棒性
補充：魯棒性（robustness）是指的穩健性或穩定性，也就是說，當某個事物受到幹擾時，這個東西的性質依舊穩定。網上有一個例子，在統計中，均值受到極端值的影響可謂非常之大，而在這種情況下中位數就要穩定得多。
補充：還有一個哨兵值的定義（也被稱為标志值、信号值和啞值），它是在特定算法中的一個特殊值，常用它來讓條件終止，由此可見它被普遍用于循環和遞歸之中。
簡而言之，哨兵就是為了簡化邊界條件的處理而存在。回頭看看連結清單的删除過程，用了兩個if來判斷，而用了哨兵值就大可不必這麼麻煩。
既然是哨兵了，那麼它站崗的位置自然也是在邊界了，對于連結清單而言，那就是頭部和尾部之間。
圖檔上下的3個箭頭請大家自行腦補成一個箭頭。
在有哨兵之前，我們必須通過l.head來通路表頭，現在可以通過l.nil.next來通路表頭了。
l.nil就是守衛連結清單疆土的哨兵，那麼l.nil.prev就自然的指向表尾了，相應的l.nil.prev指向表頭。
上面已經對删除做了修改，下面也來看看搜尋和插入。
相比删除而言，搜尋中原本就對邊界的使用不多，此處隻需将第一行的l.head換成l.nil.next和将nil換成l.nil即可。
插入
和删除一樣，邊界的判斷再也不需要了！
哨兵的作用和注意事項
通過上面有無哨兵的3個操作也可以看出來，哨兵并沒有減少算法的漸進時間界，不過可以降低常數因子，例如list-delete’和list-insert’都節約了o(1)。當然，在某些情況下，哨兵能夠降低的更多。但它更多的作用是在于使代碼更加簡潔和緊湊。
然而哨兵也需要慎用，正所謂”是藥三分毒”，如果存在很多的短小連結清單，那麼再給每一個連結清單配上一個哨兵就不劃算了，因為哨兵要占用額外的存儲空間，而短小的年表很多時，就造成了嚴重的浪費。