從 二叉搜尋樹 和 平衡二叉樹 的介紹中，可以發現二叉樹這種結構具有一個很好的特性，當有序的二叉樹構造完成之後，更改樹中節點後，隻需要的時間複雜度即可将二叉樹重新調整為有序狀态。若構造出一種具有特殊節點順序的二叉樹，使得每次對二叉樹執行插入或删除節點操作後，都調整保持二叉樹根節點的值為樹中節點的極值，則
排序算法（五）：堆排序 個元素的集合，構造出這種二叉樹後，隻需要對樹執行排序算法（五）：堆排序 次的取根節點操作，即可獲得一個有序序列。整個取節點加調整操作的時間複雜度為排序算法（五）：堆排序 ，若構造這種二叉樹的時間複雜度不高于排序算法（五）：堆排序 ，則采用構造這種二叉樹的方式來完成排序的時間複雜度為排序算法（五）：堆排序 。排序算法（五）：堆排序
堆定義
上面提到的利用具有特殊節點順序的二叉樹完成排序的方式，就是堆排序。這裡所說的節點順序是指：樹中每個節點的值都不小于（不大于）它的子節點值。堆描述的是一顆完全二叉樹，在對數組進行排序的過程中，并不是真的建構一個二叉樹結構，隻是将數組中元素下标映射到完全二叉樹，利用元素下标來表示父節點和子節點關系。
list type
tree type
通過以上兩張圖可知，堆中父子節點的下标關系為：
- 下标為 的節點，其左子節點下标為
排序算法（五）：堆排序 排序算法（五）：堆排序 - 的節點，其右子節點下标為
排序算法（五）：堆排序 排序算法（五）：堆排序 - 的節點，其父節點下标為
排序算法（五）：堆排序 排序算法（五）：堆排序
算法過程
以遞增排序為例，集合初始為待排序集合，已排序集合為空
- 構造最大堆，即調整待排序集合，使得元素映射出的完全二叉樹，滿足每個節點元素值都不小于其子節點值
- 替換待排序集合中第一個元素和最後一個元素值，即在待排序集合映射出的完全二叉樹上，将根節點值和樹中最下面一層、最右邊的節點值進行替換
- 調整堆結構使其滿足節點大小順序，标記待排序集合最後一個元素為已排序
- 重複步驟2, 3，直到待排序集合隻有一個元素
示範示例
調整為最大堆結構
要保證每個節點的值不小于其左右子節點的值，隻需要從後往前周遊集合中每個具有子節點的節點，使得其節點值不小于左右子節點的值即可（遞歸與子節點進行比較）。已知下标為
，是以具有
個元素的集合，起始周遊節點的下标為
起始待調整元素下标為 4，即值為 2 的節點
1 次調整後，下一個待調整元素下标為 3，即值為 0 的節點
2 次調整後，下一個待調整元素下标為 2，即值為 4 的節點
3 次調整後，下一個待調整元素下标為 1，即值為 3 的節點。這裡注意，節點 3 與子節點 9 比較并交換後，需要遞歸與子節點進行比較，直到值不小于子節點值
step_1
step_2
4 次調整後，下一個待調整元素下标為 0，即值為 5 的節點。同樣涉及遞歸操作
5 次調整後，目前結構即為最大堆
調整代碼
def transformToHeap(arr, index, end):
targetIndex, leftChildIndex, rightChildIndex = index, 2 * index + 1, 2 * index + 2
if leftChildIndex < end and arr[leftChildIndex] > arr[targetIndex]:
targetIndex = leftChildIndex
if rightChildIndex < end and arr[rightChildIndex] > arr[targetIndex]:
targetIndex = rightChildIndex
if not targetIndex == index:
arr[index], arr[targetIndex] = arr[targetIndex], arr[index]
transformToHeap(arr, targetIndex, end)
代碼中聲明
用于指向根節點、左右子節點中的最大節點，若需要替換節點值，則遞歸調整替換後的根節點和其左右子節點。
變量用于标志待排序集合的邊界。
疊代擷取堆頂元素
重複将待排序集合首元素和尾元素進行替換，标記替換後的尾元素為已排序，并調整堆結構使其重新成為最大堆。
起始待替換根節點為 9，第 1 次替換并調整後結構後（調整過程上面已列出）
待排序集合：[8, 7, 4, 6, 5, 1, 2, 3, 0]
已排序集合：[9]
下一個待替換根節點為 8，第 2 次替換并調整後結構後
待排序集合：[7, 6, 4, 3, 5, 1, 2, 0]
已排序集合：[8, 9]
...
下一個待替換根節點為 0，第 9 次替換并調整後結構後
待排序集合：[0]
已排序集合：[1, 2, 3, 4, 5, 6, 7, 8, 9]
觀察以上過程可知，每次排序後待排序集合元素數減一。
個元素的序列，經過
次排序後，待排序集合元素數為一，即完成排序。
疊代操作代碼
def heapSort(arr):
index = len(arr) // 2 - 1
while index >= 0:
transformToHeap(arr, index, len(arr)) # transform arr to heap arr
index = index - 1
num = 1
while num < len(arr):
arr[0], arr[-num] = arr[-num], arr[0]
transformToHeap(arr, 0, len(arr) - num) # transform arr to heap arr
num = num + 1
代碼中第一個循環為構造最大堆，第二個循環為替換待排序集合首尾元素，并調整最大堆。
算法分析
堆排序是一種不穩定排序算法，對于
個元素的序列，構造堆過程，需要周遊的元素次數為
，每個元素的調整次數為
，是以構造堆複雜度為
。疊代替換待排序集合首尾元素的次數為
，每次替換後調整次數為
，是以疊代操作的複雜度為
。由此可知堆排序的時間複雜度為
，排序過程屬于原地排序，不需要額外的存儲空間，是以空間複雜度為
github