python如何實現堆排序（程式碼範例）

這篇文章帶給大家的內容是關於python如何實現堆排序（程式碼範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法。堆積是一個近似完全二元樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或大於）它的父節點（但是不保證所有左子樹比右子樹小反之亦然）。堆排序可以說是利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節點的值都大於或等於其子節點的值，在堆排序演算法中用於升序排列；

小頂堆：每個節點的值都小於或等於其子節點的值，在堆排序演算法中用於降序排列；

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

演算法步驟

1、建立一個堆H[0……n-1]；（**對非葉子節點的子節點進行調節，建構堆**）

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

3、把堆的尺寸縮小1，並呼叫shift_down(0)，目的是把新的陣列頂端資料調整到對應位置；

4、重複步驟2，直到堆的尺寸為1。

Python 程式碼實作

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#构建堆由下往上构建所以用-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

#

以上是python如何實現堆排序（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！