推排序演算法

A. 什麼是堆排序

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

B. 堆排序過程

1，實用的排序演算法：選擇排序
（1）選擇排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在後面n-i個待排序元素中選擇排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟做完，待排序元素只剩下一個，就不用再選了。
（2）三種常用的選擇排序方法
1>直接選擇排序
2>錦標賽排序
3>堆排序
其中，直接排序的思路和實現都比較簡單，並且相比其他排序演算法，直接選擇排序有一個突出的優勢——數據的移動次數少。
（3）直接選擇排序簡介
1>直接選擇排序（select sort）是一種簡單的排序方法，它的基本步驟是：
1）在一組元素V[i]~V[n-1]中選擇具有最小排序碼的元素；
2）若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素對調；
3）在這組元素中剔除這個具有最小排序碼的元素，在剩下的元素V[i+1]~V[n-1]中重復執行1、2步驟，直到剩餘元素只有一個為止。
2>直接選擇排序使用注意
它對一類重要的元素序列具有較好的效率，這就是元素規模很大，而排序碼卻比較小的序列。因為對這種序列進行排序，移動操作所花費的時間要比比較操作的時間大的多，而其他演算法移動操作的次數都要比直接選擇排序來的多，直接選擇排序是一種不穩定的 排序方法。
3>直接選擇排序C++函數代碼

//函數功能，直接選擇排序演算法對數列排序
//函數參數，數列起點，數列終點
void dselect_sort(const int start, const int end) {
for (int i = start; i < end; ++i) {
int min_position = i;
for (int j = i + 1; j <= end; ++j) { //此循環用來尋找最小關鍵碼
if (numbers[j] < numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己與自己交換
swap(numbers[min_position], numbers[i]);

（4）關於錦標賽排序
直接選擇排序中，當n比較大時，排序碼的比較次數相當多，這是因為在後一趟比較選擇時，往往把前一趟已經做過的比較又重復了一遍，沒有把前一趟的比較結果保留下來。
錦標賽排序（tournament sort）克服了這一缺點。它的思想與體育比賽類似，就是把待排序元素兩兩進行競賽，選出其中的勝利者，之後勝利者之間繼續競賽，再選出其中的勝利者，然後重復這一過程，最終構造出勝者樹，從而實現排序的目的。

2，堆排序的排序過程
（1）個人理解：堆排序是選擇排序的一種，所以它也符合選擇排序的整體思想。直接選擇排序是在還未成序的元素中逐個比較選擇，而堆排序是首先建立一個堆（最大堆或最小堆），這使得數列已經「大致」成序，之後只需要局部調整來重建堆即可。建立堆及重建堆這一過程映射到數組中，其實就是一個選擇的過程，只不過不是逐個比較選擇，而是藉助完全二叉樹來做到有目的的比較選擇。這也是堆排序性能優於直接選擇排序的一個體現。
（2）堆排序分為兩個步驟：
1>根據初始輸入數據，利用堆的調整演算法形成初始堆；
2>通過一系列的元素交換和重新調整堆進行排序。
（3）堆排序的排序思路
1>前提，我們是要對n個數據進行遞增排序，也就是說擁有最大排序碼的元素應該在數組的末端。
2>首先建立一個最大堆，則堆的第一個元素heap[0]具有最大的排序碼，將heap[0]與heap[n-1]對調，把具有最大排序碼的元素交換到最後，再對前面n-1個元素，使用堆的調整演算法siftDown(0,n-2)，重新建立最大堆。結果具有次最大排序碼的元素又浮到堆頂，即heap[0]的位置，再對調heap[0]與heap[n-2]，並調用siftDown(0，n-3)，對前n-2個元素重新調整，……如此反復，最後得到一個數列的排序碼遞增序列。
（4）堆排序的排序過程：
下面給出局部調整成最大堆的函數實現siftDown()，這個函數在前面最小堆實現博文中的實現思路已經給出，只需做微小的調整即可用在這里建立最大堆。

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

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

D. 大根堆排序演算法的基本操作是什麼

（2）大根堆排序演算法的基本操作：①建堆，建堆是不斷調整堆的過程，從len/2處開始調整，一直到第一個節點，此處len是堆中元素的個數

E. 堆排序時間復雜度是什麼

堆排序時間復雜度，主要在每次選取最大數之後，重新建堆的過程以及初始化堆過程。

堆排序是指利用堆積樹這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。

堆是一個優先順序隊列，對於大頂堆而言，堆頂元素的權值最大。將待排序的數組建堆，然後不斷地刪除堆頂元素，就實現了排序。

堆的操作

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

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

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

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

F. 堆排序是什麼

堆排序（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個關鍵字即可以使得文件遞增有序。

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

G. 排序演算法概述

十大排序演算法：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序、希爾排序、計數排序，基數排序，桶排序

穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；
不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；
排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，前一個鍵排序的結果可以為後一個鍵排序所用。

演算法的復雜度往往取決於數據的規模大小和數據本身分布性質。
時間復雜度 ： 一個演算法執行所耗費的時間。
空間復雜度 ：對一個演算法在運行過程中臨時佔用存儲空間大小的量度。
常見復雜度由小到大 ：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

在各種不同演算法中，若演算法中語句執行次數(佔用空間)為一個常數，則復雜度為O(1)；
當一個演算法的復雜度與以2為底的n的對數成正比時，可表示為O(log n)；
當一個演算法的復雜度與n成線性比例關系時，可表示為O (n)，依次類推。

冒泡、選擇、插入排序需要兩個for循環，每次只關注一個元素，平均時間復雜度為
（一遍找元素O(n)，一遍找位置O(n)）
快速、歸並、堆基於分治思想，log以2為底，平均時間復雜度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相關
而希爾排序依賴於所取增量序列的性質，但是到目前為止還沒有一個最好的增量序列 。例如希爾增量序列時間復雜度為O(n²)，而Hibbard增量序列的希爾排序的時間復雜度為 ， 有人在大量的實驗後得出結論;當n在某個特定的范圍後希爾排序的最小時間復雜度大約為n^1.3。

從平均時間來看，快速排序是效率最高的：
快速排序中平均時間復雜度O(nlog n)，這個公式中隱含的常數因子很小，比歸並排序的O(nlog n)中的要小很多，所以大多數情況下，快速排序總是優於合並排序的。

而堆排序的平均時間復雜度也是O(nlog n)，但是堆排序存在著重建堆的過程，它把根節點移除後，把最後的葉子結點拿上來後需要重建堆，但是，拿上的值是要比它的兩個葉子結點要差很多的，一般要比較很多次，才能回到合適的位置。堆排序就會有很多的時間耗在堆調整上。

雖然快速排序的最壞情況為排序規模（n）的平方關系，但是這種最壞情況取決於每次選擇的基準， 對於這種情況，已經提出了很多優化的方法，比如三取樣劃分和Dual-Pivot快排。
同時，當排序規模較小時，劃分的平衡性容易被打破，而且頻繁的方法調用超過了O(nlog n)為
省出的時間，所以一般排序規模較小時，會改用插入排序或者其他排序演算法。

一種簡單的排序演算法。它反復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。這個工作重復地進行直到沒有元素再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為元素會經由交換慢慢「浮」到數列的頂端。
1.從數組頭開始，比較相鄰的元素。如果第一個比第二個大(小)，就交換它們兩個；
2.對每一對相鄰元素作同樣的工作，從開始第一對到尾部的最後一對，這樣在最後的元素應該會是最大(小)的數；
3.重復步驟1~2，重復次數等於數組的長度，直到排序完成。

首先，找到數組中最大（小）的那個元素；
其次，將它和數組的第一個元素交換位置（如果第一個元素就是最大（小）元素那麼它就和自己交換）；
再次，在剩下的元素中找到最大（小）的元素，將它與數組的第二個元素交換位置。如此往復，直到將整個數組排序。
這種方法叫做選擇排序，因為它在不斷地選擇剩餘元素之中的最大（小）者。

對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
為了給要插入的元素騰出空間，我們需要將插入位置之後的已排序元素在都向後移動一位。
插入排序所需的時間取決於輸入中元素的初始順序。例如，對一個很大且其中的元素已經有序（或接近有序）的數組進行排序將會比對隨機順序的數組或是逆序數組進行排序要快得多。
總的來說，插入排序對於部分有序的數組十分高效，也很適合小規模數組。

一種基於插入排序的快速的排序演算法。簡單插入排序對於大規模亂序數組很慢，因為元素只能一點一點地從數組的一端移動到另一端。例如，如果主鍵最小的元素正好在數組的盡頭，要將它挪到正確的位置就需要N-1 次移動。
希爾排序為了加快速度簡單地改進了插入排序，也稱為縮小增量排序，同時該演算法是突破O(n^2）的第一批演算法之一。
希爾排序是把待排序數組按一定數量的分組，對每組使用直接插入排序演算法排序；然後縮小數量繼續分組排序，隨著數量逐漸減少，每組包含的元素越來越多，當數量減至 1 時，整個數組恰被分成一組，排序便完成了。這個不斷縮小的數量，就構成了一個增量序列。

在先前較大的增量下每個子序列的規模都不大,用直接插入排序效率都較高，盡管在隨後的增量遞減分組中子序列越來越大,由於整個序列的有序性也越來越明顯,則排序效率依然較高。
從理論上說，只要一個數組是遞減的，並且最後一個值是1，都可以作為增量序列使用。有沒有一個步長序列,使得排序過程中所需的比較和移動次數相對較少,並且無論待排序列記錄數有多少,演算法的時間復雜度都能漸近最佳呢？但是目前從數學上來說，無法證明某個序列是「最好的」。
常用的增量序列
希爾增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N為原始數組的長度，這是最常用的序列，但卻不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表達式為

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法的一個非常典型的應用。
對於給定的一組數據，利用遞歸與分治技術將數據序列劃分成為越來越小的半子表，在對半子表排序後，再用遞歸方法將排好序的半子表合並成為越來越大的有序序列。
為了提升性能，有時我們在半子表的個數小於某個數（比如15）的情況下，對半子表的排序採用其他排序演算法，比如插入排序。
若將兩個有序表合並成一個有序表，稱為2-路歸並，與之對應的還有多路歸並。

快速排序（Quicksort）是對冒泡排序的一種改進，也是採用分治法的一個典型的應用。
首先任意選取一個數據（比如數組的第一個數）作為關鍵數據，我們稱為基準數(Pivot)，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序，也稱為分區（partition）操作。
通過一趟快速排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數組變成有序序列。
為了提升性能，有時我們在分割後獨立的兩部分的個數小於某個數（比如15）的情況下，會採用其他排序演算法，比如插入排序。

基準的選取：最優的情況是基準值剛好取在無序區數值的中位數，這樣能夠最大效率地讓兩邊排序，同時最大地減少遞歸劃分的次數，但是一般很難做到最優。基準的選取一般有三種方式，選取數組的第一個元素，選取數組的最後一個元素，以及選取第一個、最後一個以及中間的元素的中位數（如4 5 6 7, 第一個4, 最後一個7, 中間的為5, 這三個數的中位數為5, 所以選擇5作為基準）。
Dual-Pivot快排：雙基準快速排序演算法，其實就是用兩個基準數, 把整個數組分成三份來進行快速排序，在這種新的演算法下面，比經典快排從實驗來看節省了10%的時間。

許多應用程序都需要處理有序的元素，但不一定要求他們全部有序，或者不一定要一次就將他們排序，很多時候，我們每次只需要操作數據中的最大元素（最小元素），那麼有一種基於二叉堆的數據結構可以提供支持。
所謂二叉堆，是一個完全二叉樹的結構，同時滿足堆的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。在一個二叉堆中，根節點總是最大（或者最小）節點。
堆排序演算法就是抓住了這一特點，每次都取堆頂的元素，然後將剩餘的元素重新調整為最大（最小）堆，依次類推，最終得到排序的序列。

推論1：對於位置為K的結點 左子結點=2 k+1 右子結點=2 (k+1)
驗證：C:2 2 2+1=5 2 (2+1)=6
推論2：最後一個非葉節點的位置為 (N/2)-1，N為數組長度。
驗證：數組長度為6，(6/2)-1=2

計數排序對一定范圍內的整數排序時候的速度非常快，一般快於其他排序演算法。但計數排序局限性比較大，只限於對整數進行排序，而且待排序元素值分布較連續、跨度小的情況。
計數排序是一個排序時不比較元素大小的排序演算法。
如果一個數組里所有元素都是整數，而且都在0-K以內。對於數組里每個元素來說，如果能知道數組里有多少項小於或等於該元素，就能准確地給出該元素在排序後的數組的位置。

桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，利用某種函數的映射關系將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序）。
桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做排序即可。

常見的數據元素一般是由若干位組成的，比如字元串由若干字元組成，整數由若干位0~9數字組成。基數排序按照從右往左的順序，依次將每一位都當做一次關鍵字，然後按照該關鍵字對數組排序，同時每一輪排序都基於上輪排序後的結果；當我們將所有的位排序後，整個數組就達到有序狀態。基數排序不是基於比較的演算法。
基數是什麼意思？對於十進制整數，每一位都只可能是0~9中的某一個，總共10種可能。那10就是它的基，同理二進制數字的基為2；對於字元串，如果它使用的是8位的擴展ASCII字元集，那麼它的基就是256。

基數排序 vs 計數排序 vs 桶排序

基數排序有兩種方法：
MSD 從高位開始進行排序
LSD 從低位開始進行排序
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶
計數排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數值

有時，待排序的文件很大，計算機內存不能容納整個文件，這時候對文件就不能使用內部排序了（我們一般的排序都是在內存中做的，所以稱之為內部排序，而外部排序是指待排序的內容不能在內存中一下子完成，它需要做內外存的內容交換），外部排序常採用的排序方法也是歸並排序，這種歸並方法由兩個不同的階段組成：
採用適當的內部排序方法對輸入文件的每個片段進行排序，將排好序的片段（成為歸並段）寫到外部存儲器中（通常由一個可用的磁碟作為臨時緩沖區），這樣臨時緩沖區中的每個歸並段的內容是有序的。
利用歸並演算法，歸並第一階段生成的歸並段，直到只剩下一個歸並段為止。

例如要對外存中4500個記錄進行歸並，而內存大小隻能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六個有序的歸並段
每個歸並段的大小是750個記錄，並將這些歸並段全部寫到臨時緩沖區（由一個可用的磁碟充當）內了，這是第一步的排序結果。
完成第二步該怎麼做呢？這時候歸並演算法就有用處了。

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

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

一般做法是這樣：

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

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

(8)推排序演算法擴展閱讀：

堆的操作

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

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

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

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

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