Python實(shí)現(xiàn)堆排序

一、堆排序簡介

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

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

關(guān)于二叉樹和完全二叉樹的介紹可以參考：http://m.fzitv.net/article/222487.htm

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

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

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

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

二、堆排序原理

堆排序的原理如下：

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

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

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

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

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

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

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

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

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

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

4. 重復(fù)對下一個(gè)節(jié)點(diǎn)進(jìn)行比較。7小于45，交換位置。

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

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

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

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

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

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

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

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

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

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

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

# coding=utf-8
def heap_sort(array):
    first = len(array) // 2 - 1
    for start in range(first, -1, -1):
        # 從下到上，從右到左對每個(gè)非葉節(jié)點(diǎn)進(jìn)行調(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é)點(diǎn)有右子節(jié)點(diǎn)，并且右子節(jié)點(diǎn)的值大于左子節(jié)點(diǎn)，則將child變?yōu)橛易庸?jié)點(diǎn)的索引
        if child + 1 <= end and array[child] < array[child + 1]:
            child += 1
        if array[root] < array[child]:
            # 交換節(jié)點(diǎn)與子節(jié)點(diǎn)中較大者的值
            array[root], array[child] = array[child], array[root]
            # 交換值后，如果存在孫節(jié)點(diǎn)，則將root設(shè)置為子節(jié)點(diǎn)，繼續(xù)與孫節(jié)點(diǎn)進(jìn)行比較
            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))

運(yùn)行結(jié)果：

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

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

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

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

1. 時(shí)間復(fù)雜度

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

2. 穩(wěn)定性

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

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

最新評論