建堆演算法

❶ 我看書上堆排序，每次都要重新建堆，然後再調外根節點和最後一個結點，感覺這樣好麻煩你們是怎麼做的呢

堆排序很重要的一個步驟是初始建堆，它保證了樹中的每個子樹的根結點都比其下的子結點大。
建堆後的過程基本上就是選擇出最大值，然後將被交換到根結點位置的結點進行下沉的過程。而這些過程雖然對樹的局部結構進行了調整，但嚴格來說，不算是重新建堆。
《演算法導論》上對堆排序講得很詳細。它把堆排序演算法分成了三個子演算法：
一個將結點下沉的遞歸演算法；一個初始建堆演算法和一個排序演算法。
具體過程是：
1、初始建堆演算法調用結點下沉遞歸演算法完成建堆；
2、排序演算法在建好的堆上得到根結點(即最大值)，然後調用結點下沉的遞歸演算法將交換到根結點位置的結點進行下沉。反復第2步，整個演算法就完成了。
思路很清晰，可以去看看。

❷ 用一組｛14，15，30，28，5，10｝關鍵字序列，寫出初始建堆過程圖示，再根據初始堆寫出堆排序過程圖示。

起始序列為14，15，30，28，5，10，

(1)因此起始堆的情況如下：
14
15 30
28 5 10

(2)假設是打算得到一個從小到大的c，所以需要建大頂堆，起始狀態從下向上建堆：
第一步： 第二步：
14 30
28 30 28 14
25 5 10 25 5 10

(3)此時已經建立完了初始的堆。此時堆頂元素30即為最大元素，將堆頂元素與堆最後
一個元素進行交換，此時30是最大元素位於隊尾，因此無需繼續排序。所以堆如下圖
所示：10 28 14 25 5

(4)此時由於除被交換到堆頂的10以外其他的都基本有序，所以自上而下建堆得到的堆
如下：
28
25 14
10 5

(5)重復（3）和（4）步驟確定了28的位置並得到堆如下：
25
10 14
5

(6)重復（3）和（4）步驟確定了25的位置並得到堆如下：
14
10 5

(7)重復（3）和（4）步驟確定了14的位置並得到堆如下：
10
5

(8)重復（3）和（4）步驟確定了10的位置,此時只有一個數5也位於了堆的第一個位置，
因此排序完成。

(2)建堆演算法擴展閱讀：

建堆效率

n個結點的堆，高度d =log2n。根為第0層，則第i層結點個數為2^i，考慮一個元素在堆中向下移動的距離。大約一半的結點深度為d-1，不移動（葉）。四分之一的結點深度為d-2，而它們至多能向下移動一層。樹中每向上一層，結點的數目為前一層的一半，而子樹高度加一。

這種演算法時間代價為Ο（n)

由於堆有log n層深，插入結點、刪除普通元素和刪除最小元素的平均時間代價和時間復雜度都是

Ο（log n）。

操作實現

在程序中，堆用於動態分配和釋放程序所使用的對象。在以下情況中調用堆操作：

1.事先不知道程序所需對象的數量和大小。

2.對象太大，不適合使用堆棧分配器。

堆使用運行期間分配給代碼和堆棧以外的部分內存。

傳統上，操作系統和運行時庫隨附了堆實現。當進程開始時，操作系統創建稱為進程堆的默認堆。如果沒有使用其他堆，則使用進程堆分配塊。

語言運行時庫也可在一個進程內創建單獨的堆。（例如，C 運行時庫創建自己的堆。）除這些專用堆外，應用程序或許多載入的動態鏈接庫 (DLL) 之一也可以創建並使用單獨的堆。Win32 提供了一組豐富的API用於創建和使用專用堆。有關堆函數的優秀教程，請參閱 MSDN 平台 SDK 節點。

❸ 堆排序中建堆過程時間復雜度O(n)怎麼來的

建堆演算法是從最後一個非葉子結點開始下溯(即 Max-Heapify操作)，也可以把建堆過程想成先對左子樹建堆(T(n/2))，再對右子樹建堆(T(n/2))，最後對根下溯(O(lg n))

❹ 在堆排序的過程中為什麼要從n/2到1的順序進行建堆過程而不是反過來

【概念】堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
【起源】
1991年的計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發明了著名的堆排序演算法（ Heap Sort )。
【簡介】
堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特徵，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
①建堆，建堆是不斷調整堆的過程，從len/2處開始調整，一直到第一個節點，此處len是堆中元素的個數。建堆的過程是線性的過程，從len/2到0處一直調用調整堆的過程，相當於o(h1)+o(h2)…+o(hlen/2) 其中h表示節點的深度，len/2表示節點的個數，這是一個求和的過程，結果是線性的O(n)。
②調整堆：調整堆在構建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節點i和它的孩子節點left(i),right(i)，選出三者最大(或者最小)者，如果最大（小）值不是節點i而是它的一個孩子節點，那邊交互節點i和該節點，然後再調用調整堆過程，這是一個遞歸的過程。調整堆的過程時間復雜度與堆的深度有關系，是lgn的操作，因為是沿著深度方向進行調整的。
③堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據元素構建堆。然後將堆的根節點取出(一般是與最後一個節點進行交換)，將前面len-1個節點繼續進行堆調整的過程，然後再將根節點取出，這樣一直到所有節點都取出。堆排序過程的時間復雜度是O(nlgn)。因為建堆的時間復雜度是O(n)（調用一次）；調整堆的時間復雜度是lgn，調用了n-1次，所以堆排序的時間復雜度是O(nlgn)[2]
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止
【特點】
堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄
【演算法分析】
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
平均性能：O(N*logN)。
其他性能：由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。堆排序是就地排序，輔助空間為O(1）。它是不穩定的排序方法。（排序的穩定性是指如果在排序的序列中，存在前後相同的兩個元素的話，排序前 和排序後他們的相對位置不發生變化）。

❺ 堆排序是怎麼建堆的 關鍵字序列 42 13 24 91 23 16 05 88是怎樣建堆的

首先把所有數據填進一個完全二叉樹中。然後對非終端結點n/2向下進行調整。建小根堆的時候方法是：1.元素下調。比較它與兩個孩子的大小。哪個孩子比它小也比兄弟小則把它調到那個孩子的位置。然後再判斷該位置還要不要往下調。2.從n/2開始，對它之前的所有元素進行1操作。
本題解法為（按完全二叉樹寫）
一。把所有元素寫進完全二叉樹中得
42
13 24
91 23 16 05
88

二。1.對非葉子元素進行調整，即第n/2個元素，即本題的91.
因為91的孩子為88.比91小。所以調到88的位置。即91和88換
42
13 24
88 23 16 05
91

2.對n/2前一個元素進行調整。即本題的24.因為16和05都比24小，而05比16小，所以24和05調
42
13 05
88 23 16 24
91

3.對步驟2之前的一個元素，即本題的13進行調整，因為88和23都比13大，所以不用調。
4.對步驟3之前的一個元素，即本題的42進行調整。因為13和05都比42小，二05比13小。所以05和42調換位置。而調換位置後42的兒子為16和24,16比24小。所以42和16換位置。（此時已經對第一個元素進行了調整，就可以結束了，如果沒錯的話就是最終結果）
05
13 16
88 23 42 24
91
建的是小根堆，如果要建大根堆的話，也是往下調，但比較的是下面的哪個大。其他同理

❻ 數據結構與演算法--堆和堆排序

堆排序是一種原地的、時間復雜度為 O(nlogn) 的排序演算法。

堆是一種特殊的樹。
只要滿足這兩點，它就是一個堆：

對於每個節點的值都大於等於子樹中每個節點值的堆，我們叫做 「大頂堆」 。對於每個節點的值都小於等於子樹中每個節點值的堆，我們叫做 「小頂堆」 。

完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。下標可以直接計算出左右字數的下標。（數組中下標為 i 的節點，左子節點下標為 i∗2 ，右子節點下標為 i∗2+1，父節點的下標為 i/2​ 。）

如果我們把新插入的元素放到堆的最後，你可以看我畫的這個圖，是不是不符合堆的特性了？於是，我們就需要進行調整，讓其重新滿足堆的特性，這個過程我們起了一個名字，就叫做 堆化（heapify） 。
堆化實際上有兩種，從下往上和從上往下。這里我先講從下往上的堆化方法。
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。

我們把最後一個節點放到堆頂，然後利用同樣的父子節點對比方法。對於不滿足父子節點大小關系的，互換兩個節點，並且重復進行這個過程，直到父子節點之間滿足大小關系為止。這就是 從上往下的堆化方法 。

一個包含 n 個節點的完全二叉樹，樹的高度不會超過 log2​n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，也就是 O(logn)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以，往堆中插入一個元素和刪除堆頂元素的時間復雜度都是 O(logn)。

這里我們藉助於堆這種數據結構實現的排序演算法，就叫做堆排序。這種排序方法的時間復雜度非常穩定，是 O(nlogn)，並且它還是原地排序演算法。

從後往前處理數組，並且每個數據都是從上往下堆化。
因為葉子節點往下堆化只能自己跟自己比較，所以我們直接從最後一個非葉子節點開始，依次堆化就行了。

建堆的時間復雜度就是 O(n)。 推導過程見 極客時間--數據結構與演算法之美

建堆結束之後，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。我們把它跟最後一個元素交換，那最大元素就放到了下標為 n 的位置。
這個過程有點類似上面講的「刪除堆頂元素」的操作，當堆頂元素移除之後，我們把下標為 n 的元素放到堆頂，然後再通過堆化的方法，將剩下的 n−1 個元素重新構建成堆。堆化完成之後，我們再取堆頂的元素，放到下標是 n−1 的位置，一直重復這個過程，直到最後堆中只剩下標為 1 的一個元素，排序工作就完成了。

整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序演算法。堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是 O(n)，排序過程的時間復雜度是 O(nlogn)，所以，堆排序整體的時間復雜度是 O(nlogn)。
堆排序不是穩定的排序演算法，因為在排序的過程，存在將堆的最後一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。

堆這種數據結構幾個非常重要的應用：優先順序隊列、求 Top K 和求中位數。

假設我們有 100 個小文件，每個文件的大小是 100MB，每個文件中存儲的都是有序的字元串。我們希望將這些 100 個小文件合並成一個有序的大文件。這里就會用到優先順序隊列。
這里就可以用到優先順序隊列，也可以說是堆。我們將從小文件中取出來的字元串放入到小頂堆中，那堆頂的元素，也就是優先順序隊列隊首的元素，就是最小的字元串。我們將這個字元串放入到大文件中，並將其從堆中刪除。然後再從小文件中取出下一個字元串，放入到堆中。循環這個過程，就可以將 100 個小文件中的數據依次放入到大文件中。

我們可以用優先順序隊列來解決。我們按照任務設定的執行時間，將這些任務存儲在優先順序隊列中，隊列首部（也就是小頂堆的堆頂）存儲的是最先執行的任務。

如何在一個包含 n 個數據的數組中，查找前 K 大數據呢？我們可以維護一個大小為 K 的小頂堆，順序遍歷數組，從數組中取出數據與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，並且將這個元素插入到堆中；如果比堆頂元素小，則不做處理，繼續遍歷數組。這樣等數組中的數據都遍歷完之後，堆中的數據就是前 K 大數據了。

中位數，顧名思義，就是處在中間位置的那個數。
使用兩個堆：一個大頂堆， 一個小頂堆。 小頂堆中的數據都大於大頂堆中的數據。
如果新加入的數據小於等於大頂堆的堆頂元素，我們就將這個新數據插入到大頂堆；否則，我們就將這個新數據插入到小頂堆。
也就是說，如果有 n 個數據，n 是偶數，我們從小到大排序，那前 2n​ 個數據存儲在大頂堆中，後 2n​ 個數據存儲在小頂堆中。這樣，大頂堆中的堆頂元素就是我們要找的中位數。如果 n 是奇數，情況是類似的，大頂堆就存儲 2n​+1 個數據，小頂堆中就存儲 2n​ 個數據。

極客時間--數據結構與演算法之美--28 | 堆和堆排序：為什麼說堆排序沒有快速排序快？