數據結構堆排序演算法

A. 堆和堆排序

1，堆是一個完全二叉樹；
完全二叉樹要求除了最後一層，其他層的節點都是滿的，最後一層的節點都靠左排列。
2，堆中每個節點都必須大於等於（或小於等於）其子樹中每個節點的值。
堆中每個節點的值都大於等於（或者小於等於）其左右子節點的值。
3，對於每個節點的值都大於等於子樹中每個節點值的堆，叫作「大頂堆」。對於每個節點的值都小於等於子樹中每個節點值的堆，叫「小頂堆」。

要實現一個堆，要先知道堆都支持哪些操作，已及如何存儲一個堆。
1，如何存儲一個堆：
完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。因為不需要存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。
2，往堆中插入一個元素
往堆中插入一個元素後，需要繼續滿足堆的兩個特性
（1）如果把新插入的元素放到堆的最後，則不符合堆的特性了，於是需要進行調整，讓其重新滿足堆的特性，這個過程叫做 堆化（heapify）
（2）堆化實際上有兩種，從下往上和從上往下
（3）從下往上的堆化方法：
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。

（1）從堆的定義的第二條中，任何節點的值都大於等於（或小於等於）子樹節點的值，則堆頂元素存儲的就是堆中數據的最大值或最小值。
（2）假設是大頂堆，堆堆頂元素就是最大的元素，但刪除堆頂元素之後，就需要把第二大元素放到堆頂，那第二大元素肯定會出現在左右子節點中。然後在迭代地刪除第二大節點，以此類推，直到葉子節點被刪除。

但這種方式會使堆化出來的堆不滿足完全二叉樹的特性
（3）可以把最後一個節點放到堆頂，然後利用同樣的父子節點對比方法，對於不滿足父子節點大小關系的，互換兩個節點，並且重復進行這個過程，直到父子節點之間滿足大小關系為止，這是從上往下的堆化方法。

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

（1）排序方法有時間復雜度是O(n^2)的冒泡排序，插入排序，選擇排序，有時間復雜度是O（nlogn）的歸並排序，快速排序，線性排序。

（2）藉助堆這種數據結構實現的排序演算法就叫作堆排序，這種排序方法的時間復雜度非常穩定，是O(nlogn)，並且它還是原地排序演算法。
堆排序的過程大致分解為兩大步驟：建堆和排序
（3）建堆：
1，首先將數組原地建成一個堆。「原地」：是指不藉助另一個數組，就在原地數組上操作。
2，建堆有兩種思路：
第一種：在堆中插入一個元素的思路。
盡管數組中包含n個數據，但是可以假設起初堆中只包含一個數據，就是下標為1的數據。然後，調用插入方法，將將下標從2到n的數據依次插入到堆中，這樣就將包含n個數據的數組，組織成了堆
第二種：是從後往前處理數組，並且每個數據都是從上往下堆化。
第二種和第一種思路截然相反，第一種建堆思路的處理過程是從前往後處理數據，並且每個數據插入堆中時，都是從下往上堆化。
對下標從n/2開始到1的數據進行堆化，下標是n/2 + 1到n的節點，是葉子節點，不需堆化
3，建堆的時間復雜度
每個節點堆化的時間復雜度是O(logn)，則n/2+1個節點堆化的總時間復雜度是O(n)。
①：因為葉子節點不需要堆化，所以需要堆化的節點從倒數第二層開始。每個節點堆化的過程中，需要比較和交換的節點個數，跟這個節點高度k成正比。
（4）排序：
建堆結束後，數組中的數據已是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。
將它和最後一個元素交換，最大元素就放到了下標為n的位置
這個過程有點類似「刪除堆頂元素」的操作，當堆頂元素移除後，把下標為n的元素放到堆頂，然後在通過堆化的方法，將剩下的n-1個元素重新構建成堆。堆化完成之後，在取堆頂元素，放到下標是n-1的位置，一直重復這個過程，直到最後堆中只剩下標為1的一個元素，排序工作就完成了。

（5）時間，空間復雜度，以及穩定性分析
①：整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序演算法。
②：堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是O(n)，排序過程的時間復雜度是O(nlogn),所以堆排序的時間復雜度是O(nlogn)
③：堆排序不是穩定的排序演算法，可能改變值相等的數據原始相對順序。

B. 計算機二級的中的「堆排序法」是怎麼排的

堆排序就是將所有待排序的元素組成一個堆，然後不斷彈出堆頂的元素並調用函數維持堆序，直到所有元素均被彈出後，排序完成。被彈出的元素序列即一個有序數列。

一般做法是這樣：

當一個節點被插入時，將該節點放在堆的末尾（這是為了保證堆是完全二叉樹）然後將該節點與它的父節點比較，看該節點是否大於（或小於）其父節點，即判斷當前的堆是否滿足堆序。如果不滿足，則將該節點與其父節點交換。

再將該節點與其新的父節點做比較，依此類推，直到該節點不再需要與其父節點交換為止。（即滿足堆序時停止） 當一個根節點被彈出（即被從堆中刪除）時，將堆最尾部的節點移動到頭結點的位置，然後將該節點不斷與其子節點比較，如果不符合堆序則交換，直到符合堆序為止。

(2)數據結構堆排序演算法擴展閱讀：

堆的操作

堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：

最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點

創建最大堆（Build Max Heap）：將堆中的所有數據重新排序

堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

C. 數據結構的排序演算法中，哪些排序是穩定的，哪些排序是不穩定的

一、穩定排序演算法

1、冒泡排序

2、雞尾酒排序

3、插入排序

4、桶排序

5、計數排序

6、合並排序

7、基數排序

8、二叉排序樹排序

二、不穩定排序演算法

1、選擇排序

2、希爾排序

3、組合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

一個排序演算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。

做這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個對象間之比較，就會被決定使用在原先數據次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。

(3)數據結構堆排序演算法擴展閱讀：

排序演算法的分類：

1、通過時間復雜度分類

計算的復雜度（最差、平均、和最好性能），依據列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且壞的性能是 O(n^2)。對於一個排序理想的性能是 O(n)。

而僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要 O(nlogn)。

2、通過空間復雜度分類

存儲器使用量（空間復雜度）（以及其他電腦資源的使用）

3、通過穩定性分類

穩定的排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。

D. 什麼是堆排序

【概念】堆排序(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）。它是不穩定的排序方法。（排序的穩定性是指如果在排序的序列中，存在前後相同的兩個元素的話，排序前 和排序後他們的相對位置不發生變化）。

E. 數據結構的排序方法有哪些

題目似乎不是很完整。
先回答：（1）C，（2）A，（3）D，(4)B，(5)G
(1) C．插入排序 法從未排序的序列中依次取出元素，與已排序序列(初始時為空)中的元素作比較，將其放入已排序序列的正確位置上；
(2) A．選擇排序 法從未排序的序列中挑選元素， 並將其依次放入已排序序列(初始時為空)的一端；交換排序方法是對序列中的元素進行一系列比較， 當被比較的兩元素逆序時，進行交換；
(3) D．起泡排序 和 （4）B．快速排序 是基於這類方法的兩種排序方法；
(5) G．堆排序 法是基於選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。

原題應該是：
排序方法有許多種，（1）法從未排序的序列中依次取出元素，與已排序序列（初始時為空）中的元素作比較，將其放入已排序序列的正確位置上；（2）法從未排序的序列中挑選元素，並將其依次放入已排序序列（初始時為空）的一端； 交換排序方法是對序列中的元素進行一系列比較，當被比較的兩元素逆序時，進行交換；（3）和（4）是基於這類方法的兩種排序方法， 而（4）是比（3）效率更高的方法；（5）法是基於選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。 【北方交通大學 1999 一、3 （5分）】
（1）--（5）: A．選擇排序 B．快速排序 C．插入排序 D．起泡排序
E．歸並排序 F．shell排序 G．堆排序 H．基數排序
【解答】（1）C，（2）A，（3）D，(4)B，(5)G

F. 數據結構有哪些基本演算法

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法

G. 數據結構中堆排序，快速排序，歸並排序排序的時間復雜度順序快慢依次是什麼

堆排序 平均時間：O(n*logn) 最壞：O(n*logn)
快速排序 平均時間：O(n*logn) 最壞：O(n的平方)
歸並排序 平均時間：O(n*logn) 最壞：O(n的平方)
排序演算法沒有最快情況的說法。

從平均性能來說，快速排序最佳，因為所需時間最短，但快速排序在最壞情況下的時間性能不如堆排序和歸並排序。n較大時，歸並排序所需時間較堆排序省，但歸並排序需要的輔助存儲量更大。

H. 什麼是堆排序呢，其時間復雜度是怎麼計算的呢

堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。
堆排序的平均時間復雜度為O(nlogn)，空間復雜度為θ(1)。

I. 數據結構中有哪些基本演算法

數據結構中最基本的演算法有：查找、排序、快速排序，堆排序，歸並排序，，二分搜索演算法
等等。

1、用的最多也是最簡單的數據結構是線性表。

2、有前途的又難數據結構是圖 。

3、常用的80％演算法是排序和查找。

J. 堆排序是什麼

堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄
其過程為：
（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）大根堆排序演算法的基本操作：

① 初始化操作：將R[1..n]構造為初始堆；

②
每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆（亦稱重建堆）。

注意：

①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。

②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止