建堆的演算法

⑴ 求一計算機數據結構題解

以最大堆為例,給一個建堆的演算法,
樓主要的保持堆的性質的演算法,只要選取其中一段程序就行了~~~

//******************
// 6.3_1 建堆
// Date 2007.02.13
//******************

#include <iostream>
using namespace std;

const int maxn = 1000;

void max_heapify( int A[maxn], int i, int heap_size )
{
int l, r, largest, temp;

l = 2 * i;
r = 2 * i + 1;

if (( l <= heap_size ) && ( A[l] > A[i] ))
largest = l;
else
largest = i;
if (( r <= heap_size ) && ( A[r] > A[largest] ))
largest = r;
if ( largest != i ) {
temp = A[i];
A[i] = A[largest];
A[largest] = temp;

max_heapify( A, largest, heap_size );
}
}

void build_max_heap( int A[maxn], int n )
{
int i;

for (i = n / 2; i >= 1; i--)
max_heapify( A, i, n );
}

int main()
{
int i, n;
int A[maxn];

cin >> n;

for (i = 1; i <= n; i++)
cin >> A[i];

build_max_heap( A, n );

for (i = 1; i < n; i++)
cout << A[i] << ' ';

cout << A[n] << endl;

return 0;
}

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

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

⑶ 堆排序是怎麼建堆的 關鍵字序列 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
建的是小根堆，如果要建大根堆的話，也是往下調，但比較的是下面的哪個大。其他同理

⑷ 如何判斷一個序列是否為堆

堆可以看成一棵完全二叉樹：

任一根節點>=左右孩子（或者<=）（大的叫大根堆，小的叫小根堆。）注意一個堆中的這種性質有一致性，不能既有大於又有小於情況存在。

這題你應該是理解錯題意了，首先，大根堆是一個完全二叉樹，根節點大於左右節點，利用堆的性質來看選項A：

91為根節點，下面掛兩個子節點85、53。然後以85為根節點，下面掛兩個子節點36、47，以53為根節點，下面掛兩個子節點30，24。

以此類推，得到選項C是正確答案。

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

堆是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：

1、堆中某個節點的值總是不大於或不小於其父節點的值；

2、堆總是一棵完全二叉樹。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。堆是線性數據結構，相當於一維數組，有唯一後繼。

一、堆的演算法思想

不必將值一個個地插入堆中，通過交換形成堆。假設根的左、右子樹都已是堆，並且根的元素名為R。這種情況下，有兩種可能：

（1） R的值小於或等於其兩個子女，此時堆已完成；

（2） R的值大於其某一個或全部兩個子女的值，此時R應與兩個子女中值較小的一個交換，結果得到一個堆，除非R仍然大於其新子女的一個或全部的兩個。

這種情況下，我們只需簡單地繼續這種將R「拉下來」的過程，直至到達某一個層使它小於它的子女，或者它成了葉結點。

二、堆的定義

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆。

(ki<= k2i,ki<= k2i+1)或者(ki>= k2i,ki>= k2i+1), (i = 1,2,3,4...n/2)

若將和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。

由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。

⑸ 建堆的時間復雜度到底是多少

建最大堆或者最小堆都是O(N),不是O(NlogN)，這個證明在演算法導論第3版 88頁有證明。
建立完堆後，就開始交換堆頂元素和最後一個元素，叫做出堆，出堆後需要再次維護堆頂，這一步時間復雜度是logN。

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

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

⑺ 為什麼堆排序構建堆的時間復雜度是N,而重調堆的時間復雜度是logN

建堆的時候你看看是不是多次調用了調堆的函數呢，那肯定就不只是logN了，如果從底部最後的父節點開始建堆，那麼我們可以大概算一下：
假如有N個節點，那麼高度為H=logN，最後一層每個父節點最多隻需要下調1次，倒數第二層最多隻需要下調2次，頂點最多需要下調H次，而最後一層父節點共有2^(H-1)個,倒數第二層公有2^(H-2),頂點只有1(2^0)個，所以總共的時間復雜度為s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 將H代入後s= 2N - 2 - log2(N)，近似的時間復雜度就是O(N)。

⑻ 用一組｛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也位於了堆的第一個位置，
因此排序完成。

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

建堆效率

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

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

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

Ο（log n）。

操作實現

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

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

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

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

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

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