Python實現(xiàn)堆排序

一、堆排序簡介

堆排序(Heap Sort)是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設計的一種排序算法。

堆的結(jié)構(gòu)是一棵完全二叉樹的結(jié)構(gòu)，并且滿足堆積的性質(zhì)：每個節(jié)點(葉節(jié)點除外)的值都大于等于(或都小于等于)它的子節(jié)點。

關于二叉樹和完全二叉樹的介紹可以參考：http://www.fzitv.net/article/222487.htm

堆排序先按從上到下、從左到右的順序?qū)⒋判蛄斜碇械脑貥?gòu)造成一棵完全二叉樹，然后對完全二叉樹進行調(diào)整，使其滿足堆積的性質(zhì)：每個節(jié)點(葉節(jié)點除外)的值都大于等于(或都小于等于)它的子節(jié)點。構(gòu)建出堆后，將堆頂與堆尾進行交換，然后將堆尾從堆中取出來，取出來的數(shù)據(jù)就是最大(或最小)的數(shù)據(jù)。重復構(gòu)建堆并將堆頂和堆尾進行交換，取出堆尾的數(shù)據(jù)，直到堆中的數(shù)據(jù)全部被取出，列表排序完成。

堆結(jié)構(gòu)分為大頂堆和小頂堆：

1. 大頂堆：每個節(jié)點(葉節(jié)點除外)的值都大于等于其子節(jié)點的值，根節(jié)點的值是所有節(jié)點中最大的，所以叫大頂堆，在堆排序算法中用于升序排列。

2. 小頂堆：每個節(jié)點(葉節(jié)點除外)的值都小于等于其子節(jié)點的值，根節(jié)點的值是所有節(jié)點中最小的，所以叫小頂堆，在堆排序算法中用于降序排列。

二、堆排序原理

堆排序的原理如下：

1. 將待排序列表中的數(shù)據(jù)按從上到下、從左到右的順序構(gòu)造成一棵完全二叉樹。

2. 將完全二叉樹中每個節(jié)點(葉節(jié)點除外)的值與其子節(jié)點(子節(jié)點有一個或兩個)中較大的值進行比較，如果節(jié)點的值小于子節(jié)點的值，則交換他們的位置(大頂堆，小頂堆反之)。

3. 將節(jié)點與子節(jié)點進行交換后，要繼續(xù)比較子節(jié)點與孫節(jié)點的值，直到不需要交換或子節(jié)點是葉節(jié)點時停止。比較完所有的非葉節(jié)點后，即可構(gòu)建出堆結(jié)構(gòu)。

4. 將數(shù)據(jù)構(gòu)造成堆結(jié)構(gòu)后，將堆頂與堆尾交換，然后將堆尾從堆中取出來，添加到已排序序列中，完成一輪堆排序，堆中的數(shù)據(jù)個數(shù)減1。

5. 重復步驟2,3,4，直到堆中的數(shù)據(jù)全部被取出，列表排序完成。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 進行升序排列為例。列表的初始狀態(tài)如下圖。

要進行升序排序，則構(gòu)造堆結(jié)構(gòu)時，使用大頂堆。

1. 將待排序列表中的數(shù)據(jù)按從上到下、從左到右的順序構(gòu)造成一棵完全二叉樹。

2. 從完全二叉樹的最后一個非葉節(jié)點開始，將它的值與其子節(jié)點中較大的值進行比較，如果值小于子節(jié)點則交換。24是最后一個非葉子節(jié)點，它只有一個子節(jié)點21，24大于21，不需要交換。

3. 繼續(xù)將倒數(shù)第二個非葉節(jié)點的值與其子節(jié)點中較大的值進行比較，如果值小于子節(jié)點則交換。節(jié)點30有兩個子節(jié)點5和36，較大的是36，30小于36，交換位置。

4. 重復對下一個節(jié)點進行比較。7小于45，交換位置。

5. 繼續(xù)重復，50大于27，不需要交換位置。如果不需要進行交換，則不用再比較子節(jié)點與孫節(jié)點。

6. 繼續(xù)重復，17小于45，交換位置。

7. 17和45交換位置之后，17交換到了子節(jié)點的位置，還需要繼續(xù)將其與孫節(jié)點進行比較。17大于15，不需要交換。

8. 繼續(xù)對下一個節(jié)點進行比較，10小于50，交換位置。

9. 10和50交換位置之后，10交換到了子節(jié)點的位置，還需要繼續(xù)將其與孫節(jié)點進行比較。10小于于27，交換位置。

10. 此時，一個大頂堆構(gòu)造完成，滿足了堆積的性質(zhì)：每個節(jié)點(葉節(jié)點除外)的值都大于等于它的子節(jié)點。

11. 大頂堆構(gòu)建完成后，將堆頂與堆尾交換位置，然后將堆尾從堆中取出。將50和21交換位置，交換后21到了堆頂，50(最大的數(shù)據(jù))到了堆尾，然后將50從堆中取出。

12. 將50從堆中取出后，找到了待排序列表中的最大值，50添加到已排序序列中，第一輪堆排序完成，堆中的元素個數(shù)減1。

13. 取出最大數(shù)據(jù)后，重復將完全二叉樹構(gòu)建成大頂堆，交換堆頂和堆尾，取出堆尾。這樣每次都是取出當前堆中最大的數(shù)據(jù)，添加到已排序序列中，直到堆中的數(shù)據(jù)全部被取出。

14. 循環(huán)進行 n 輪堆排序之后，列表排序完成。排序結(jié)果如下圖。

三、Python實現(xiàn)堆排序

# coding=utf-8
def heap_sort(array):
    first = len(array) // 2 - 1
    for start in range(first, -1, -1):
        # 從下到上，從右到左對每個非葉節(jié)點進行調(diào)整，循環(huán)構(gòu)建成大頂堆
        big_heap(array, start, len(array) - 1)
    for end in range(len(array) - 1, 0, -1):
        # 交換堆頂和堆尾的數(shù)據(jù)
        array[0], array[end] = array[end], array[0]
        # 重新調(diào)整完全二叉樹，構(gòu)造成大頂堆
        big_heap(array, 0, end - 1)
    return array
 
 
def big_heap(array, start, end):
    root = start
    # 左孩子的索引
    child = root * 2 + 1
    while child <= end:
        # 節(jié)點有右子節(jié)點，并且右子節(jié)點的值大于左子節(jié)點，則將child變?yōu)橛易庸?jié)點的索引
        if child + 1 <= end and array[child] < array[child + 1]:
            child += 1
        if array[root] < array[child]:
            # 交換節(jié)點與子節(jié)點中較大者的值
            array[root], array[child] = array[child], array[root]
            # 交換值后，如果存在孫節(jié)點，則將root設置為子節(jié)點，繼續(xù)與孫節(jié)點進行比較
            root = child
            child = root * 2 + 1
        else:
            break
 
 
if __name__ == '__main__':
    array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
    print(heap_sort(array))

運行結(jié)果：

[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

代碼中，先實現(xiàn)一個big_heap(array, start, end)函數(shù)，用于比較節(jié)點與其子節(jié)點中的較大者，如果值小于子節(jié)點的值則進行交換。代碼中不需要真正將數(shù)據(jù)都添加到完全二叉樹中，而是根據(jù)待排序列表中的數(shù)據(jù)索引來得到節(jié)點與子節(jié)點的位置關系。完全二叉樹中，節(jié)點的索引為i，則它的左子節(jié)點的索引為2*i+1，右子節(jié)點的索引為2*i+2，有n個節(jié)點的完全二叉樹中，非葉子節(jié)點有n//2個，列表的索引從0開始，所以索引為0~n//2-1的數(shù)據(jù)為非葉子節(jié)點。

實現(xiàn)堆排序函數(shù)heap_sort(array)時，先調(diào)用big_heap(array, start, end)函數(shù)循環(huán)對非葉子節(jié)點進行調(diào)整，構(gòu)造大頂堆，然后將堆頂和堆尾交換，將堆尾從堆中取出，添加到已排序序列中，完成一輪堆排序。然后循環(huán)構(gòu)建大頂堆，每次將最大的元素取出，直到堆中的數(shù)據(jù)全部被取出。

四、堆排序的時間復雜度和穩(wěn)定性

1. 時間復雜度

在堆排序中，構(gòu)建一次大頂堆可以取出一個元素，完成一輪堆排序，一共需要進行n輪堆排序。每次構(gòu)建大頂堆時，需要進行的比較和交換次數(shù)平均為logn(第一輪構(gòu)建堆時步驟多，后面重建堆時步驟會少很多)。時間復雜度為 T(n)=nlogn ，再乘每次操作的步驟數(shù)(常數(shù)，不影響大O記法)，所以堆排序的時間復雜度為 O(nlogn) 。

2. 穩(wěn)定性

在堆排序中，會交換節(jié)點與子節(jié)點，如果有相等的數(shù)據(jù)，可能會改變相等數(shù)據(jù)的相對次序。所以堆排序是一種不穩(wěn)定的排序算法。

到此這篇關于Python實現(xiàn)堆排序案例詳解的文章就介紹到這了,更多相關Python實現(xiàn)堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論