本篇文章將介紹堆排序算法在 Python 中的實(shí)現(xiàn)。

Python中的堆排序算法

堆排序是一種強(qiáng)大的算法，用于在 Python 中對數(shù)組和列表進(jìn)行排序。 它很受歡迎，因?yàn)樗浅？?，并且不像合并排序和快速排序那樣占用任何額外空間。

堆排序的時間復(fù)雜度是 O(n*log(n)) 。

堆排序是一種就地算法，它不再創(chuàng)建任何數(shù)據(jù)結(jié)構(gòu)來保存數(shù)據(jù)的中間狀態(tài)。 相反，它對我們的原始數(shù)組進(jìn)行了更改。

因此，當(dāng)數(shù)據(jù)非常大時，這為我們節(jié)省了大量空間。

該算法唯一的缺點(diǎn)是它非常不穩(wěn)定。 如果我們的數(shù)組中有多個元素在不同索引處具有相同的值，則它們的位置將在排序時發(fā)生變化。

堆排序算法的工作原理是遞歸地創(chuàng)建一個最小或最大堆，取出根節(jié)點(diǎn)，將其放在我們數(shù)組中的第一個未排序索引處，并將最后一個堆元素轉(zhuǎn)換為根節(jié)點(diǎn)。

這個過程遞歸重復(fù)，直到我們在堆中留下一個節(jié)點(diǎn)。 最后，最后一個堆元素被放置在我們數(shù)組的最后一個索引處。

如果我們想一想，這個過程類似于選擇排序算法，因?yàn)槲覀內(nèi)∽畲笾祷蜃钚≈挡⑺鼈兎旁谝雅判驍?shù)組的頂部。

在 Python 中實(shí)現(xiàn)堆排序算法

我們將首先了解實(shí)現(xiàn) build_heap() 函數(shù)，該函數(shù)采用原始數(shù)組、數(shù)組的長度和父節(jié)點(diǎn)的索引。 在這里，如果我們查看一個數(shù)組，最后一個父節(jié)點(diǎn)的索引位于我們數(shù)組內(nèi)的 (n//2 - 1) 處。

類似地，該特定父級的左孩子的索引為 2*parent_index + 1 ，右孩子的索引為 2*parent_index + 2 。

在這個例子中，我們試圖創(chuàng)建一個最大堆。 這意味著每個父節(jié)點(diǎn)都需要大于其子節(jié)點(diǎn)。

為此，我們將從最后一個父節(jié)點(diǎn)開始，向上移動到堆的根節(jié)點(diǎn)。 如果我們想創(chuàng)建一個最小堆，我們希望所有父節(jié)點(diǎn)都小于它們的子節(jié)點(diǎn)。

此 build_heap() 函數(shù)將檢查左或右子節(jié)點(diǎn)是否大于當(dāng)前父節(jié)點(diǎn)，并將最大節(jié)點(diǎn)與父節(jié)點(diǎn)交換。

該函數(shù)遞歸地調(diào)用自身，因?yàn)槲覀兿Ｍ麑Χ阎械乃懈腹?jié)點(diǎn)遞增地重復(fù)之前的過程。

以下代碼片段演示了上述 built_heap() 函數(shù)在 Python 中的有效實(shí)現(xiàn)。

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2
    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index
    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index
    if largest_index != parent_index:
        arr[parent_index],arr[largest_index] = arr[largest_index],arr[parent_index]
        build_heap(arr, length, largest_index)

現(xiàn)在，我們有一個函數(shù)，它獲取數(shù)組中的最大值并將其放在堆的根部。 我們需要一個函數(shù)來獲取未排序的數(shù)組，調(diào)用 build_heap() 函數(shù)并從堆中提取元素。

以下代碼片段演示了 heapSort() 函數(shù)在 Python 中的實(shí)現(xiàn)。

def heapSort(arr):
    length = len(arr)
    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)
    for element_index in range(length-1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)

我們在數(shù)組中逐步調(diào)用每個父節(jié)點(diǎn)的 build_heap() 函數(shù)。 請注意，我們將 length//2-1 作為起始索引，-1 作為結(jié)束索引，步長為 -1。

這意味著我們從最后一個父節(jié)點(diǎn)開始，遞減索引 1，直到到達(dá)根節(jié)點(diǎn)。

第二個 for 循環(huán)從我們的堆中提取元素。 它也從最后一個索引開始，并在我們數(shù)組的第一個索引處停止。

我們在此循環(huán)中交換數(shù)組的第一個和最后一個元素，并通過傳遞 0 作為根索引對新排序的數(shù)組執(zhí)行 build_heap() 函數(shù)。

現(xiàn)在，我們已經(jīng)編寫了用 Python 實(shí)現(xiàn)堆排序的程序。 是時候?qū)?shù)組進(jìn)行排序并測試上面編寫的代碼了。

arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

輸出:

Sorted array : [1, 2, 3, 4, 5, 6]

如我們所見，我們的數(shù)組已完全排序。 這意味著我們的代碼工作得很好。

如果我們想按降序排序，我們可以創(chuàng)建一個最小堆而不是上面實(shí)現(xiàn)的最大堆。

本文不會解釋最小堆，因?yàn)樗呀?jīng)在本教程的開頭討論了最小堆是什么。

我們的程序以下列方式工作。 以下塊顯示了我們的數(shù)組在代碼執(zhí)行的每個階段的狀態(tài)。

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

build_heap() 函數(shù)執(zhí)行了 3 次，因?yàn)槲覀兊亩阎兄挥?3 個父節(jié)點(diǎn)。

之后，我們的元素提取階段獲取第一個元素，將其與最后一個元素交換，然后再次執(zhí)行 build_heap() 函數(shù)。 對長度 - 1 重復(fù)此過程，我們的數(shù)組得到排序。

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

最新評論