python 堆排序

genedna 發(fā)布于2019-07-31 11:18 / 2225人閱讀

摘要：堆排序堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆排序可以說是一種利用堆的概念來排序的選擇排序。代碼實(shí)現(xiàn)構(gòu)建堆由下往上構(gòu)建所以用每次踢掉求出的最大值

堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)（但是不保證所有左子樹比右子樹小反之亦然）。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；

小頂堆：每個節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；

堆排序的平均時間復(fù)雜度為 Ο(nlogn)。

算法步驟

創(chuàng)建一個堆 H[0……n-1]；（**對非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行調(diào)節(jié)，構(gòu)建堆**）

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；

重復(fù)步驟 2，直到堆的尺寸為 1。

Python 代碼實(shí)現(xiàn)

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#構(gòu)建堆由下往上構(gòu)建所以用-1
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1 #每次踢掉求出的最大值
        heapify(arr, 0)
    return arr