Java/堆的路徑
Heap ADT diagram!implementation
堆是一種特殊的樹，它恰好是優先佇列的有效實現。此圖顯示了本章中資料結構之間的關係。
figure=figs/heap_adt.eps
通常，我們儘量在 ADT 和其實現之間保持儘可能多的距離，但在堆的情況下，這種界限會略微失效。原因是我們對實現操作的效能感興趣。對於每個實現，有一些操作很容易實現並且效率很高，而另一些則很笨拙且緩慢。
事實證明，樹的陣列實現作為堆的實現特別有效。陣列執行良好的操作正是我們用來實現堆的操作。
為了理解這種關係，我們將分幾步進行。首先，我們需要開發比較各種實現效能的方法。接下來，我們將看看堆執行的操作。最後，我們將比較優先佇列的堆實現與其他實現（陣列和列表），並瞭解為什麼堆被認為特別高效。
performance analysis run time algorithm analysis
當我們比較演算法時，我們希望有一種方法來判斷一個演算法何時比另一個演算法快，或者佔用更少的空間，或者使用更少的其他資源。很難詳細回答這些問題，因為演算法的時間和空間使用情況取決於演算法的實現、正在解決的具體問題以及程式執行的硬體。
本節的目的是開發一種討論效能的方式，該方式獨立於所有這些因素，只取決於演算法本身。首先，我們將關注執行時間；稍後我們將討論其他資源。
我們的決定受到一系列約束的指導
列舉
首先，演算法的效能取決於它執行的硬體，因此我們通常不會以秒之類的絕對值來談論執行時間。相反，我們通常計算演算法執行的抽象操作次數。
其次，效能通常取決於我們試圖解決的具體問題——有些問題比其他問題更容易。為了比較演算法，我們通常專注於最壞情況或平均（或常見）情況。
第三，效能取決於問題的規模（通常，但並非總是，集合中的元素數量）。我們透過將執行時間表示為問題規模的函式來明確地解決這種依賴關係。
最後，效能取決於實現的細節，例如物件分配開銷和方法呼叫開銷。我們通常會忽略這些細節，因為它們不會影響抽象運算元量隨問題規模增加的速率。
列舉
為了使這個過程更具體，請考慮我們已經看到的兩種用於對整數陣列進行排序的演算法。第一個是選擇排序，我們在排序部分看到過。以下是我們在那裡使用的虛擬碼。
逐字
selectionsort (array)
for (int i=0; i<array.length; i++)
// find the lowest item at or to the right of i
// swap the ith item and the lowest item
逐字
為了執行虛擬碼中指定的操作，我們編寫了名為 findLowest 和 swap 的輔助方法。在虛擬碼中，findLowest 如下所示
逐字
// find the index of the lowest item between // i and the end of the array
findLowest (array, i)
// lowest contains the index of the lowest item so far
lowest = i;
for (int j=i+1; j<array.length; j++)
// compare the jth item to the lowest item so far
// if the jth item is lower, replace lowest with j
return lowest;
逐字
交換如下所示
逐字
swap (i, j)
// store a reference to the ith card in temp
// make the ith element of the array refer to the jth card
// make the jth element of the array refer to temp
逐字
為了分析這種演算法的效能，第一步是決定要計算哪些操作。顯然，程式做了很多事情：它遞增 i，將它與牌組的長度進行比較，它搜尋陣列中最大的元素，等等。不清楚什麼是正確的計算物件。
sorting selection sort
事實證明，一個不錯的選擇是比較兩個專案的次數。許多其他選擇最終會產生相同的結果，但這很容易做到，我們發現它使我們能夠最容易地與其他排序演算法進行比較。
下一步是定義“問題大小”。在本例中，自然選擇是陣列的大小，我們將其稱為 n。
最後，我們希望推匯出一個表示式，告訴我們必須執行多少個抽象操作（具體而言是比較），作為 n 的函式。
helper method
我們從分析輔助方法開始。swap 複製了幾個引用，但它沒有執行任何比較，因此我們忽略了執行交換所花費的時間。findLowest 從 i 開始遍歷陣列，將每個專案與 lowest 進行比較。我們檢視的專案數量是 n，因此比較的總數是 n。
接下來，我們考慮 findLowest 被呼叫多少次以及每次呼叫的 i 值。最後一次被呼叫時，i 是 1，因此比較次數是 1。上一次迭代執行了 2 次比較，依此類推。在第一次迭代中，i 是 n，比較次數是 n。
因此比較的總數為 1+2+3+...+n。這個和等於 n(n+1)/2。為了描述這種演算法，我們通常會忽略低階項 (n) 並說工作總量與 n^2 成正比。由於主導項是二次的，我們也可能說這種演算法是二次時間的。
quadratic time
mergesort analysis!mergesort sorting algorithm analysis
在歸併排序部分，我聲稱歸併排序花費的時間與 n log n 成正比，但我沒有解釋如何或為什麼。現在我將解釋。
同樣，我們從檢視演算法的虛擬碼開始。對於歸併排序，它是
逐字
mergeSort (array) // find the midpoint of the array // divide the array into two halves // sort the halves recursively // merge the two halves and return the result
逐字
在遞迴的每一層，我們將陣列分成兩半，進行兩次遞迴呼叫，然後合併這兩半。圖形化地，該過程如下所示
figure=figs/mergetree.eps,width=5in
圖中的每條線都是遞迴的一層。在頂部，單個數組分成兩半。在底部，陣列（每個陣列包含一個元素）合併成陣列（每個陣列包含 2 個元素）。
recursion
表格的前兩列顯示了每一層陣列的數量和每個陣列中的專案數量。第三列顯示了每一層遞迴發生的合併次數。下一列是最需要思考的：它顯示了每個合併執行的比較次數。
pseudocode
如果您檢視 merge 的虛擬碼（或您的實現），您應該相信自己，在最壞情況下，它需要 n 次比較，其中 n 是要合併的專案總數。
下一步是將每一層的合併次數乘以每次合併的工作量（比較次數）。結果是每一層的總工作量。此時，我們利用一個小技巧。我們知道最終我們只對結果中的主導項感興趣，因此我們可以直接忽略比較次數中的 n 項。如果這樣做，則每一層的總工作量只是 n。
接下來我們需要知道層數作為 n 的函式。好吧，我們從一個包含 n 個專案的陣列開始，將其分成兩半，直到它變成 1。這與從 1 開始，乘以 2 直到我們得到 n 相同。換句話說，我們想知道我們必須將 2 乘以自身多少次才能得到 n。答案是層數 k 等於 n 的以 2 為底的對數。
最後，我們將每層的總工作量 n 乘以層數 k 以獲得 n log n，如承諾的那樣。這種函式形式沒有很好的名稱；大多數時候人們只是說“n log n”。
一開始可能不明顯 n log n 比 n^2 好，但對於 n 的較大值，它確實更好。作為練習，編寫一個程式來列印 n^2 和 n log n
for a range of values of .
overhead
效能分析需要很多假設。首先，我們忽略了程式執行的大多數操作，只計算了比較。然後我們決定只考慮最壞情況效能。在分析過程中，我們隨意舍入了一些東西，當我們完成後，我們隨意丟棄了低階項。
當我們解釋這種分析的結果時，我們必須記住所有這些假設。因為歸併排序是 n log n，我們認為它比選擇排序好，但這並不意味著歸併排序總是更快。這僅僅意味著最終，如果我們對越來越大的陣列進行排序，歸併排序會勝出。
這需要多長時間取決於實現的細節，包括除了我們計算的比較之外，每個演算法執行的其他工作。這些額外工作有時被稱為開銷。它不影響效能分析，但會影響演算法的執行時間。
例如，我們實現的歸併排序實際上是在進行遞迴呼叫之前分配子陣列，然後在子數組合並後讓它們被垃圾回收。再次檢視歸併排序的圖表，我們可以看到分配的總空間量與成正比，分配的總物件數量約為。所有這些分配都需要時間。
即便如此，一個好演算法的糟糕實現往往比一個壞演算法的好實現要好。原因是對於較大的值，好演算法更好，而對於較小的值，它無關緊要，因為兩種演算法都足夠好。
作為練習，編寫一個程式來列印的值。
and for a range of values of . For what value of are they equal?
implementation!Priority Queue analysis!Priority Queue priority queue!sorted list implementation
在佇列章節中，我們查看了基於陣列的優先順序佇列實現。陣列中的專案是無序的，因此新增新專案很容易（在末尾新增），但是刪除專案比較困難，因為我們必須搜尋具有最高優先順序的專案。
另一種方法是基於排序列表的實現。在這種情況下，當我們插入新專案時，我們會遍歷列表並將新專案放在正確的位置。這種實現利用了列表的一個特性，即很容易將新節點插入中間。類似地，刪除具有最高優先順序的專案很容易，前提是我們將其保留在列表的開頭。
這些操作的效能分析很簡單。無論專案數量如何，將專案新增到陣列的末尾或從列表的開頭刪除節點都需要相同的時間。因此，兩種操作都是常數時間。
constant time
無論何時遍歷陣列或列表，對每個元素執行常數時間操作，執行時間都與專案數量成正比。因此，從陣列中刪除某項和向列表中新增某項都是線性時間。
linear time
那麼從優先順序佇列中插入和刪除專案需要多長時間呢？對於陣列實現，插入需要與成正比的時間，但刪除需要更長的時間。第一次刪除必須遍歷所有專案；第二次必須遍歷，依此類推，直到最後一次刪除，只需要檢視 1 個專案。因此，總時間為，即（仍然是）。因此，插入和刪除的總時間是線性函式和二次函式的總和。結果的領先項是二次項。
列表實現的分析類似。第一次插入不需要任何遍歷，但是此後，每次插入新專案時，我們都必須遍歷列表的一部分。通常我們不知道要遍歷列表的多少，因為這取決於資料以及插入的順序，但我們可以假設平均我們需要遍歷列表的一半。不幸的是，即使遍歷列表的一半仍然是線性操作。
因此，再次，插入和刪除專案需要與成正比的時間。因此，根據此分析，我們無法說哪種實現更好；陣列和列表都產生二次執行時間。
如果我們使用堆來實現優先順序佇列，我們可以在與成正比的時間內執行插入和刪除。因此，個專案的總時間為，這比要好。這就是為什麼在本章開頭我說堆是優先順序佇列的特別高效實現。
Heap!definition tree complete tree tree!complete heap property
堆是一種特殊的樹。它有兩個屬性，這些屬性通常不適用於其他樹
描述
[完整性：] 這棵樹是完整的，這意味著節點是從上到下，從左到右新增的，沒有留下任何空隙。
[堆性：] 樹中具有最高優先順序的專案位於樹的頂部，並且每個子樹也是如此。
描述
這兩個屬性都需要一些解釋。此圖顯示了一些被認為是完整或不完整的樹
figure=figs/tree4.eps,width=4in
空樹也被認為是完整的。我們可以透過比較子樹的高度來更嚴格地定義完整性。回想一下，樹的高度是級別數。
height
從根節點開始，如果樹是完整的，那麼左子樹的高度和右子樹的高度應該相等，或者左子樹可能高出一級。在任何其他情況下，樹都不能是完整的。
此外，如果樹是完整的，那麼子樹之間的高度關係必須對樹中的每個節點都成立。
將這些規則寫成遞迴方法是很自然的
逐字
public static boolean isComplete (Tree tree)
// the null tree is complete
if (tree == null) return true;
int leftHeight = height (tree.left);
int rightHeight = height (tree.right);
int diff = leftHeight - rightHeight;
// check the root node
if (diff < 0 diff > 1) return false;
// check the children
if (!isComplete (tree.left)) return false;
return isComplete (tree.right);
逐字
對於這個例子，我使用了樹的連結實現。作為練習，為陣列實現編寫相同的方法。同樣作為練習，編寫 height 方法。空樹的高度為 0，葉子節點的高度為 1。
recursive definition
堆屬性也類似於遞迴。為了使樹成為堆，樹中最大的值必須位於根節點，並且每個子樹也必須如此。作為另一個練習，編寫一個方法來檢查樹是否具有堆屬性。
reheapify
在插入任何專案之前，我們要從堆中刪除專案可能看起來很奇怪，但我認為刪除更容易解釋。
乍一看，我們可能會認為從堆中刪除一個專案是一個常數時間操作，因為具有最高優先順序的專案始終位於根節點。問題是，一旦我們刪除了根節點，我們剩下的東西就不再是堆了。在我們返回結果之前，我們必須恢復堆屬性。我們稱此操作為重新堆化。
情況如下圖所示
figure=figs/tree5.eps,height=2in
根節點的優先順序為 r，有兩個子樹 A 和 B。子樹 A 的根節點的值為 a，子樹 B 的根節點的值為 b。
我們假設在我們從樹中刪除 r 之前，樹是一個堆。這意味著 r 是堆中最大的值，a 和 b 是它們各自子樹中最大的值。
一旦我們刪除了 r，我們就必須將生成的樹重新變成堆。換句話說，我們需要確保它具有完整性和堆性。[檢查拼寫]。
確保完整性的最佳方法是刪除最底層的，最右邊的節點，我們將其稱為 c，並將它的值放在根節點。在一般的樹實現中，我們必須遍歷樹才能找到這個節點，但在陣列實現中，我們可以在常數時間內找到它，因為它始終是陣列中的最後一個（非空）元素。
當然，最後一個值可能不是最大的，所以將其放在根節點會破壞堆性。[檢查拼寫] 屬性。幸運的是，它很容易恢復。我們知道堆中最大的值是 a 或 b。因此，我們可以選擇較大的一個並將其與根節點的值交換。
隨意，假設 b 較大。因為我們知道它是堆中剩下的最高值，所以我們可以將其放在根節點並將 c 放在子樹 B 的頂部。現在情況如下
figure=figs/tree6.eps,height=2in
再次，c 是我們從陣列中最後一個條目複製的值，b 是堆中剩下的最高值。由於我們沒有更改子樹 A，我們知道它仍然是一個堆。唯一的問題是我們不知道子樹 B 是否是一個堆，因為我們只是在它的根節點放了一個（可能是低）值。
recursion
如果我們有一個方法可以重新堆化子樹 B 會不會很好？等等…我們有！
在堆中插入新專案是一個類似的操作，只不過我們不是從頂部向下傳遞值，而是從底部向上傳遞值。
同樣，為了保證完整性，我們將新元素新增到樹中最底層的，最右邊的位置，即陣列中的下一個可用空間。
然後，為了恢復堆屬性，我們將新值與其鄰居進行比較。情況如下
figure=figs/tree7.eps,height=2in
新值為 c。我們可以透過將 c 與 a 進行比較來恢復此子樹的堆屬性。如果 c 更小，則堆屬性就滿足了。如果 c 更大，則交換 c 和 a。交換滿足堆屬性，因為我們知道 c 也必須大於 b，因為 c > a 且 a > b。
現在子樹已經重新堆化了，我們可以向上遍歷樹，直到到達根節點。
Heap!analysis analysis!Heap
對於插入和刪除，我們執行一個常數時間操作來完成實際的插入和刪除，但之後我們必須重新堆化樹。在一種情況下，我們從根節點開始，向下遍歷，比較專案，然後遞迴地重新堆化一個子樹。在另一種情況下，我們從葉子節點開始，向上遍歷，同樣在樹的每一層比較元素。
像往常一樣，我們可能需要統計幾個操作，例如比較和交換。任何選擇都有效；真正的問題是我們檢查的樹的層數以及我們在每一層做了多少工作。在這兩種情況下，我們都會繼續檢查樹的層數，直到恢復堆屬性，這意味著我們可能只訪問一層，或者在最壞情況下，我們可能必須訪問所有層。讓我們考慮最壞的情況。
在每一層，我們只執行常數時間操作，例如比較和交換。因此，總工作量與樹的層數成正比，也就是高度。
所以我們可以說這些操作相對於樹的高度是線性的，但是我們感興趣的“問題大小”不是高度，而是堆中的專案數量。
作為n的函式，樹的高度是log₂(n+1)。這並不適用於所有樹，但對於完全樹而言是正確的。要了解原因，請考慮樹中每一層節點的數量。第一層包含 1 個，第二層包含 2 個，第三層包含 4 個，依此類推。第k層包含
nodes, and the total number in all levels up to is
2^(k-1) 個節點。換句話說，n = 2^(k-1) - 1，這意味著 k = log₂(n+1)。
logarithmic time
因此，插入和刪除都花費對數時間。插入和刪除專案需要與log₂(n+1)成正比的時間。
heapsort sorting analysis!heapsort
上一節的結果表明了另一種排序演算法。給定n個專案，我們將它們插入到一個堆中，然後將它們移除。由於堆語義，它們按順序輸出。我們已經證明了這種演算法，稱為堆排序，需要與n*log₂(n+1)成正比的時間，這比選擇排序好，與歸併排序相同。
隨著n的值變大，我們期望堆排序比選擇排序更快，但效能分析無法讓我們知道它是否會比歸併排序更快。我們會說這兩種演算法具有相同的增長階，因為它們以相同的函式形式增長。另一種說法是它們屬於同一個複雜度類。
big-O notation complexity class order of growth constant time linear time quadratic time logarithmic time
複雜度類有時用“大O符號”表示。例如，O(n²)（讀作“n平方階”）是所有增長速度不快於n²的大型n值函式的集合。說一個演算法是O(n²)等同於說它是二次的。我們已經看到其他複雜度類，按效能遞減的順序排列：
0.2in tabularll
& constant time
& logarithmic
& linear
& ``en log en
& quadratic
& exponential
tabular 0.2in
到目前為止，我們檢視過的演算法中沒有一個是指數級的。對於較大的n值，這些演算法很快變得不切實際。然而，“指數增長”這個詞在非技術語言中也經常出現。它經常被誤用，所以我希望包含它的技術含義。
人們經常使用“指數級”來描述任何增加且加速的曲線（即具有正斜率和曲率的曲線）。當然，還有許多其他曲線符合這種描述，包括二次函式（和更高階的多項式），甚至像n²這樣的溫和函式。大多數這些曲線都沒有指數的（通常是有害的）爆炸性行為。
作為一個練習，比較2^n和n²的行為，隨著n的值增加。
selection sort mergesort heapsort complexity class order of growth overhead
描述
[選擇排序:] 排序部分中的簡單排序演算法。
[歸併排序:] 歸併排序部分中的更高階排序演算法。
[堆排序:] 另一種排序演算法。
[複雜度類:] 一組演算法，其效能（通常是執行時間）具有相同的增長階。
[增長階:] 一組具有相同主導項的函式，因此對於較大的n值具有相同的定性行為。
[開銷:] 在執行效能分析中考慮的抽象操作之外執行其他操作的程式消耗的額外時間或資源。