本文實例講述了Python堆排序原理與實現方法。分享給大家供大家參考，具體如下：

在這里要事先說明一下我也是新手，很多東西我了解不是很深入，寫算法完全是鍛煉自己邏輯能力同時順帶幫助讀研的朋友么解決一些實際問題。所以很多時候考慮的東西不是很全面能請各位看到博文的大牛們指正。對于排序算法說實在的我覺得已經寫爛了，但是為什么還是要過一遍呢？還是為了能夠打牢基礎。說一下自己的看法，對于已經的玩爛的算法因該怎么學。首先最重要的還是了解算法的基本模型和算法思想，我覺得這是非常重要的。其次的話首先先嘗試自己實現算法每個步驟的功能，當遇到瓶頸的時候回去看算法思想。當你寫出來的時候就應該去網上找找有沒有更好的實現方法。編程最大的魅力在于每個人都有每個人的套路。然后去思考自己還有哪些地方寫的不夠好。寫算法實際上目標只有兩個，對基礎語法的鞏固和對算法思想的理解。

堆排序

堆

在這里首先要先解釋一下什么是堆，堆棧是計算機的兩種最基本的數據結構。堆的特點就是FIFO(first in first out)先進先出，這里的話我覺得可以理解成樹的結構。堆在接收數據的時候先接收的數據會被先彈出。

棧的特性正好與堆相反，是屬于FILO(first in/last out)先進后出的類型。棧處于一級緩存而堆處于二級緩存中。這個不是本文重點所以不做過多展開。

堆排序節點訪問和操作定義

堆節點的訪問

在這里我們借用wiki的定義來說明：

通常堆是通過一維數組來實現的。在陣列起始位置為0的情況中

(1)父節點i的左子節點在位置(2*i+1);
(2)父節點i的右子節點在位置(2*i+2);
(3)子節點i的父節點在位置floor((i-1)/2);

堆操作

堆可以分為大根堆和小根堆，這里用最大堆的情況來定義操作:

(1)最大堆調整(MAX_Heapify):將堆的末端子節點作調整，使得子節點永遠小于父節點。這是核心步驟，在建堆和堆排序都會用到。比較i的根節點和與其所對應i的孩子節點的值。當i根節點的值比左孩子節點的值要小的時候，就把i根節點和左孩子節點所對應的值交換，當i根節點的值比右孩子的節點所對應的值要小的時候，就把i根節點和右孩子節點所對應的值交換。然后再調用堆調整這個過程，可見這是一個遞歸的過程。

(2)建立最大堆(Build_Max_Heap):將堆所有數據重新排序。建堆的過程其實就是不斷做最大堆調整的過程，從len/2出開始調整，一直比到第一個節點。

(3)堆排序(HeapSort):移除位在第一個數據的根節點，并做最大堆調整的遞歸運算。堆排序是利用建堆和堆調整來進行的。首先先建堆，然后將堆的根節點選出與最后一個節點進行交換，然后將前面len-1個節點繼續做堆調整的過程。直到將所有的節點取出，對于n個數我們只需要做n-1次操作。