資料結構/最小堆和最大堆
以下是堆的一些定義
堆是一個數組，其中存在父子關係，並且子節點的索引是父節點索引的 2 倍或父節點索引的 2 倍加 1，子節點在父節點之後具有順序，這是由堆的客戶端程式注入的某種具體排序方案。在堆改變後，維護不變的順序非常重要。有些人（Sedgewick 和 Wayne）創造了“上升”和“下降”這兩個術語，其中維護不變性涉及將破壞不變性的專案向上移動到排序較低的子節點之上，然後下降到任何排序較高的子節點之下，因為可能有兩個子節點，所以一個專案可以向上移動到排序較低的子節點之上，但仍然具有另一個排序較高的子節點。
堆是一種高效的半有序資料結構，用於儲存可排序資料的集合。最小堆支援兩種操作
INSERT(heap, element) element REMOVE_MIN(heap)
（我們討論最小堆，但最小堆和最大堆之間沒有真正的區別，除了比較的解釋方式。）
本章將專門討論二叉堆，儘管存在不同型別的堆。在大多數情況下，二叉堆和堆可以互換使用。堆可以看作是一棵樹，具有父節點和子節點。堆和二叉樹的主要區別在於堆屬性。為了使一個數據結構被認為是堆，它必須滿足以下條件（堆屬性）
- 如果A 和B 是堆中的元素，並且B 是A 的子節點，則 key(A) ≤ key(B)。
（此屬性適用於最小堆。最大堆的比較將被顛倒。）這告訴我們最小鍵將始終保留在頂部，而更大的值將在其下方。由於這個事實，堆被用來實現優先順序佇列，它允許快速訪問具有最高優先順序的專案。以下是一個最小堆的示例
堆是用一個從 1 到 N 索引的陣列實現的，其中 N 是堆中元素的數量。
在任何時候，堆都必須滿足堆屬性
array[n] <= array[2*n] // parent element <= left child
和
array[n] <= array[2*n+1] // parent element <= right child
只要索引在陣列邊界內。
我們將證明array[1]是堆中的最小元素。我們透過觀察如果其他元素小於第一個元素時的矛盾來證明它。假設array[i]是最小的第一個例項，其中對於所有j < i，array[j] > array[i]，並且i >= 2。但根據堆不變性，array[floor(i/2)] <= array[i]：這是一個矛盾。
因此，很容易計算MIN(heap)
MIN(heap)
return heap.array[1];
要刪除最小元素，我們必須調整堆以填充heap.array[1]。這個過程稱為滲透。基本上，我們將洞從節點 i 移動到節點2i 或2i+1。如果我們選擇這兩個節點中的最小值，堆不變性將得到保持；假設array[2i] < array[2i+1]。然後array[2i]將被移動到array[i]，在2i處留下一個洞，但移動後array[i] < array[2i+1]，因此堆不變性得到保持。在某些情況下，2i+1將超過陣列邊界，我們被迫滲透2i。在其他情況下，2i也在邊界之外：在這種情況下，我們已經完成了。
因此，以下是最小堆的刪除演算法
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i + 1)
REMOVE_MIN(heap)
{
savemin=arr[1];
arr[1]=arr[--heapsize];
i=1;
while(i<heapsize){
minidx=i;
if(LEFT(i)<heapsize && arr[LEFT(i)] < arr[minidx])
minidx=LEFT(i);
if(RIGHT(i)<heapsize && arr[RIGHT(i)] < arr[minidx])
minidx=RIGHT(i);
if(minidx!=i){
swap(arr[i],arr[minidx]);
i=minidx;
}
else
break;
}
}
為什麼這有效？
If there is only 1 element ,heapsize becomes 0, nothing in the array is valid. If there are 2 elements , one min and other max, you replace min with max. If there are 3 or more elements say n, you replace 0th element with n-1th element. The heap property is destroyed. Choose the 2 children of root and check which is the minimum. Choose the minimum between them, swap it. Now subtree with swapped child is loose heap property. If no violations break.
INSERT 存在類似的策略：只需將元素附加到陣列，然後透過交換修復堆不變性。例如，如果我們剛剛附加了元素 N，那麼唯一可能的不變性違反涉及該元素，特別是如果，則這兩個元素必須交換，現在唯一可能的不變性違反是在
![{\displaystyle array[floor(N/2)]>array[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24c556c36e19d6cdca1424cc3846013f01027bb6)
array[floor(N/4)] and array[floor(N/2)]
我們繼續迭代，直到 N=1 或直到不變性得到滿足。
INSERT(heap, element)
append(heap.array, element)
i = heap.array.length
while (i > 1)
{
if (heap.array[i/2] <= heap.array[i])
break;
swap(heap.array[i/2], heap.array[i]);
i /= 2;
}
Merge-heap: it would take two max/min heap and merge them and return a single heap. O(n) time. Make-heap: it would also be nice to describe the O(n) make-heap operation Heap sort: the structure can actually be used to efficiently sort arrays
Make-heap 將使用一個名為 heapify 的函式
//Element is a data structure//
Make-heap(Element Arr[],int size)
{
for(j=size/2;j>0;j--)
{
Heapify(Arr,size,j);
}
}
Heapify(Element Arr[],int size,int t)
{
L=2*t;
R=2*t+1;
if(L<size )
{
mix=minindex(Arr,L,t);
if(R<=size)
mix=minindex(Arr,R,mix);
}
else
mix=t;
if(mix!=t)
{
swap(mix,t);
Heapify(Arr,size,mix);
}
}
minindex 返回較小元素的索引
在 2009 年，一個較小的排序基準測試由 OzSort 贏得，該基準測試有一篇論文清楚地描述瞭如何使用優先順序堆作為排序機來生成大型（內部）排序部分的合併部分。如果一個排序部分佔用 M 個記憶體，排序問題是 k x M 個大，那麼一次取 k 個部分中每個部分大小為 M/k 的連續部分，這樣它們就適合 M 個記憶體（k * M/k = M），併為 k 個部分中的每個部分的第一個元素建立大小為 k 的優先順序佇列，以及當刪除頂部元素並將其寫入輸出緩衝區時，從相應的部分取下一個元素。這意味著元素可能需要與它們來自的部分的標籤相關聯。當一個大小為 M/k 的部分用盡時，從儲存在磁碟上的原始排序部分載入下一個大小為 M/k 的迷你部分。繼續，直到磁碟上 k 個部分中的每個部分中的所有迷你部分都用盡。
（作為對磁碟操作延遲進行流水線的示例，存在雙輸出緩衝區，因此一旦一個輸出緩衝區已滿，一個緩衝區就會寫入磁碟，而另一個緩衝區正在被填充。）
這篇論文表明，優先順序堆比二叉樹更直接，因為元素不斷被刪除，以及作為 k 路合併的排隊機制而被新增，並且在對超過內部儲存器儲存的超大型資料集進行排序時具有實際應用。