### 正文前的扯淡
之前電話面試一個公司時，面試官讓寫一個堆排序，遺憾的是我忘了堆排序的思想了，所以直接說不會寫，這次電面也以失敗告終...知恥后勇，這幾天在網上找了很多寫堆排序的帖子，但是帖子質量不好，堆排序是什么不介紹，代碼也非常不詳細，看了半天沒整明白，不過好在今天找出了資料結構課的課本，系統復習后，嘗試用Python寫出了一個堆排序，
### 目錄
* 堆排序介紹
* 堆排序演算法詳解+Python實作
### 堆排序涉及到的概念
* 堆排序是利用 **堆**進行排序的
* **堆**是一種完全二叉樹
* **堆**有兩種型別: **大根堆** **小根堆**
* 兩種型別的概念如下：
大根堆：每個結點的值都大于或等于左右孩子結點
小根堆：每個結點的值都小于或等于左右孩子結點
因為比較抽象，所以專門花了兩個圖表示
那么，什么是完全二叉樹呢？
**完全二叉樹** 是 一種除了最后一層之外的其他每一層都被完全填充，并且所有結點都保持向左對齊的樹，向左對齊指的是：
像這樣的樹就不是完全二叉樹：
如果給上面的大小根堆的根節點從1開始編號，則滿足下面關系(下圖就滿足這個關系)：
如果把這些數字放入陣列中，則如下圖所示：其中，上面的數字是陣列下標值，第一個元素占位用，
### 堆排序演算法詳解+Python實作
了解了堆，下面我們來看下堆排序的思想是怎樣的(以大根堆為例)：
* 首先將待排序的陣列構造出一個大根堆
* 取出這個大根堆的堆頂節點(最大值)，與堆的最下最右的元素進行交換，然后把剩下的元素再構造出一個大根堆
* 重復第二步，直到這個大根堆的長度為1，此時完成排序，
### 下面通過圖片來看下，第二個步驟是如何進行的：
這就是構建大根堆的思想，了解了之后就可以進行編碼，編碼主要解決兩個問題：
* 如何把一個序列構造出一個大根堆
* 輸出堆頂元素后，如何使剩下的元素構造出一個大根堆
根據問題進行編碼，由于陣列下標是從0開始的，而樹的節點從1開始，我們還需要引入一個輔助位置，Python提供的原始資料型別list實際上是一個線性表(Array),由于我們需要在序列最左邊追加一個輔助位，線性表這樣做的話開銷很大，需要把陣列整體向右移動，所以list型別沒有提供形如`appendleft`的函式，但是在一個鏈表里做這種操作就很簡單了，Python的`collections`庫里提供了鏈表結構`deque`，我們先使用它初始化一個無序序列：
```
from collections import deque
L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
L.appendleft(0)
```
此時L如下：
```
In [2]: L
Out[2]: deque([0, 50, 16, 30, 10, 60, 90, 2, 80, 70])
```
根據我們上面找出的兩個難點，可以先編出`heap_sort`函式：
```
def heap_sort(L):
L_length = len(L) - 1
first_sort_count = L_length / 2
for i in range(first_sort_count):
heap_adjust(L, first_sort_count - i, L_length)
for i in range(L_length - 1):
L = swap_param(L, 1, L_length - i)
heap_adjust(L, 1, L_length - i - 1)
return [L[i] for i in range(1, len(L))]
```
講解：
* 因為引入了一個輔助空間，所以使`L_length = len(L) - 1`
* 第一個回圈做的事情是把序列調整為一個大根堆(`heap_adjust`函式)
* 第二個回圈是把堆頂元素和堆末尾的元素交換(`swap_param`函式)，然后把剩下的元素調整為一個大根堆(`heap_adjust`函式)
我們要排序的序列為`deque([50, 16, 30, 10, 60, 90, 2, 80, 70])`,但是在第一個回圈中，我們用了一個輔助變數`first_sort_count`,回圈時，這個值變化的順序是**4->3->2->1**,這是為什么呢，實際上，這些數字代表的是有孩子的節點，從下圖可以看出，而我們所謂的調整大根堆，其實就是按照從右往左，從下到上的順序，把每顆小樹調整為一個大根堆，**4->3->2->1**的調整，其實就是**10->30->16->50**的調整，
**swap_param**函式很簡單，我們根據Python的特點，無需引入中間變數，直接交換堆頂元素和最后元素即可，代碼如下：
```
def swap_param(L, i, j):
L[i], L[j] = L[j], L[i]
return L
```
下面讓我們看下最關鍵的堆調整函式`heap_adjust`：
```
def heap_adjust(L, start, end):
temp = L[start]
i = start
j = 2 * i
while j <= end:
if (j < end) and (L[j] < L[j + 1]):
j += 1
if temp < L[j]:
L[i] = L[j]
i = j
j = 2 * i
else:
break
L[i] = temp
```
這段代碼比較抽象，我們結合實際例子把自己想象成一個解釋器來看一下：
* 第一個回圈在第一個呼叫這個函式時，start=4, end=9,L=[0, 50, 16, 30, 10, 60, 90, 2, 80, 70],進行`temp = L[start]`,實際就是temp=L[4]=10,`i=start`， i此時為4，拿到我們要處理的樹節點，`j = 2*i`，j此時得到第四個節點的左子樹坐標，接著開始回圈，回圈條件`j <= end`代表在調整完整棵樹樹之前一直進行回圈，第一個條件`if (j < end) and (L[j] < L[j + 1])`是要保證 **j** 取到較大子樹的坐標，由于左子樹大于右子樹，所以這個**if**運算式不進行，
第二個**if** 運算式，要做的如果根節點小于子樹的值，就把根節點和較大的子樹的值進行交換，`temp<L[j]` ：**10<80**，所以執行if內的陳述句：`L[i] = L[j]` **執行后L[i]為80**，`i = j` **執行后i=8**，`j = 2 * i`,**執行后j為16**，此時不滿足回圈條件，退出回圈，然后執行`L[i] = temp`,**執行后L[i] = 10**，
這個函式其實就是把每個子樹的根節點和較大的子節點進行值交換，而且如果在左子樹 依然是根節點的情況下繼續進行調整， 讀者可以自己照著圖調整幾次就可以很好的理解代碼的含義了，
這樣調整4次后，這棵樹就變成了一個大根堆，此時序列變成了這樣：
接下來進行第二個回圈，
```
for i in range(L_length - 1):
L = swap_param(L, 1, L_length - i)
heap_adjust(L, 1, L_length - i - 1)
```
首先`L = swap_param(L, 1, L_length - i)`交換第一個節點和最后一個節點的值(因為我們引入了一個輔助空間，所以序列長度減1)，此時序列變成了**[16, 80, 50, 70, 60, 30, 2, 10, 90]** 接下來對**[16, 80, 50, 70, 60, 30, 2, 10]**進行調整，由于我們之前已經把序列調整為了大根堆，所以此時回圈條件變為從堆頂進行小范圍調整就可以，
這次調整后，堆變為：
然后繼續把10和80進行交換，繼續調整，直到遍歷完整個序列為止，
完整代碼如下：
```
from collections import deque
def swap_param(L, i, j):
L[i], L[j] = L[j], L[i]
return L
def heap_adjust(L, start, end):
temp = L[start]
i = start
j = 2 * i
while j <= end:
if (j < end) and (L[j] < L[j + 1]):
j += 1
if temp < L[j]:
L[i] = L[j]
i = j
j = 2 * i
else:
break
L[i] = temp
def heap_sort(L):
L_length = len(L) - 1
first_sort_count = L_length / 2
for i in range(first_sort_count):
heap_adjust(L, first_sort_count - i, L_length)
for i in range(L_length - 1):
L = swap_param(L, 1, L_length - i)
heap_adjust(L, 1, L_length - i - 1)
return [L[i] for i in range(1, len(L))]
def main():
L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
L.appendleft(0)
print heap_sort(L)
if __name__ == '__main__':
main()
```
運行結果如下：
```
python heap_sort2.py
[2, 10, 16, 30, 50, 60, 70, 80, 90]
```
推薦一下我建的python學習交流扣扣qun：850973621，群里有免費的視頻教程，開發工具、
電子書籍、專案原始碼分享，一起交流學習，一起進步！
一些小專案游戲
電子書籍
作者：一根薯條
鏈接：https://www.jianshu.com/p/d174f1862601
來源：簡書
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/232879.html
標籤：Python