調整建堆演算法

Ⅰ 如何根據一個數組建立最大堆

最大堆：根結點的鍵值是所有堆結點鍵值中最大者的堆。 最小堆：根結點的鍵值是所有堆結點鍵值中最小者的堆。 而最大-最小堆集結了最大堆和最小堆的優點，這也是其名字的由來。 最大-最小堆是最大層和最小層交替出現的二叉樹，即最大層結點的兒子屬於最小層，最小層結點的兒子屬於最大層。 以最大（小）層結n點為根結點的子樹保有最大（小）堆性質：根結點的鍵值為該子樹結點鍵值中最大（小）項。 主要操作不失一般性，只討論根結點為最小層的情況。插入 只需要將節點插在二叉樹的最後一個葉子結點位置，然後比較它對它父親節點的大小，如果大則停止；如果小則交換位置，然後對父親節點遞歸該過程直至根節點。復雜度為O(log(n))。 一般來說，插入的位置可以不是最後一個葉子節點，可以作為任意中間節點的孩子節點插入，將這個葉子節點變為中間節點後，按上文所說的方法調整節點順序以保證維持堆特性不變。刪除 要從堆中刪除一個節點，用最後一個節點替換掉根節點，然後調整節點順序以維持堆特性。建堆既可以用堆調整方法將原數組調整為一個堆，也可以藉助往堆中插入元素的方法從無到有的建立一個堆。兩種方法比較：（1）藉助堆調整建堆的時間復雜度為O(n)。藉助插入法建堆的時間復雜度為O(nlgn) ，書上第二問要求證明這個復雜度，但是我認為插入法的復雜度也是O（n），因為它和堆調整的區別在於針對每個節點i，堆調整是自上向下進行調整，插入法是自下向上進行調整。（2）對於同樣的輸入兩個方法建立的堆可能不同。因為堆調整時，是i要跟它的兩個子女進行比較，選出最大（小）的，但是插入x時，x只跟它的父節點進行比較。比如輸入為2、3、4，堆調整建堆為4、3、2，插入法建堆為4、2、3。插入法建最大堆代碼如下：

Ⅱ 堆排序的簡介

堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特徵，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
（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) ①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1）.
它是不穩定的排序方法。（排序的穩定性是指如果在排序的序列中，存在前後相同的兩個元素的話，排序前 和排序後他們的相對位置不發生變化）

Ⅲ 在堆排序的過程中為什麼要從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 | 堆和堆排序：為什麼說堆排序沒有快速排序快？

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

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

Ⅶ 堆排序的堆是怎麼建立的

堆排序，也叫二叉堆排序。
完全二叉樹：
1、左右子樹的節點數滿足 Ln/Rn=1
2、左右子樹高度滿足 Rh+1>=Lh>=Rh
3、子節點值統一比父節點大（小）。

最大堆：2叉樹的所有子節點都比父節點小。所以根節點是最大的。
最小堆：2叉樹的所有子節點都比父節點大。所以根節點是最小的。

建堆：假設最多有N個數據。開辟一段用來存這N個數據的空間。根節點位置為0。其子節點位置為1、2。所有子節點位置與父節點的位置（k）關系：k，2k+1，2k+2。 假設已經有了n個數據，那麼新數據自然放在n位（因為位置是從0開始），定義一個函數 shift_up() 用來調整新數據。它的功能是：將新數據與 (n-1)/2 位置的數據（新數據的父節點）比較，如果比父節點大，那麼就交換，繼續比較，直到它比父節點小。

重新建堆： 當取數據時，就是將根節點取出來。因為根節點是最大的，所以自然還要將其所有子節點進行調整，以保證剩下的數據的根節點是最大的。方法是：將最後一個數放到根節點位置（因為根節點取出後，根節點就空了），然後調用 shift_down()函數將其與1、2位置的數比較，如果比它大，則交換，然後繼續與2k+1，2k+2位置的比較，直到這兩個位置的數都比它小。

Ⅷ 數據結構，堆排序，建堆過程，向上調整法和向下調整法有什麼區別和聯系

向上調整是由空堆，逐個插入元素，來建立初始堆，向下調整是從n/2的位置，倒著將編號n/2,n/2-1,...,1直到編號為1的結點調成堆後，初始堆構建完成。它們沒有多大的區別，只不過初始堆有些元素所在的位置不同而已。