Python實現(xiàn)堆排序的方法詳解
本文實例講述了Python實現(xiàn)堆排序的方法。分享給大家供大家參考，具體如下：
堆排序作是基本排序方法的一種，類似于合并排序而不像插入排序，它的運行時間為O(nlogn)，像插入排序而不像合并排序，它是一種原地排序算法，除了輸入數(shù)組以外只占用常數(shù)個元素空間。
堆（定義）：（二叉）堆數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組對象，可以視為一棵完全二叉樹。如果根結(jié)點的值大于（小于）其它所有結(jié)點，并且它的左右子樹也滿足這樣的性質(zhì)，那么這個堆就是大（小）根堆。
我們假設(shè)某個堆由數(shù)組A表示，A[1]為樹的根，給定某個結(jié)點的下標(biāo)i，其父結(jié)點、左孩子、右孩子的下標(biāo)都可以計算出來：
PARENT(i):
return i/2
LEFT(i):
return 2i
RIGHT(i):
return 2i+1
堆排序Python實現(xiàn)
所謂堆排序的過程，就是把一些無序的對象，逐步建立起一個堆的過程。
下面是用Python實現(xiàn)的堆排序的代碼：
def build_max_heap(to_build_list):
"""建立一個堆"""
# 自底向上建堆
for i in range(len(to_build_list)/2 - 1, -1, -1):
max_heap(to_build_list, len(to_build_list), i)
def max_heap(to_adjust_list, heap_size, index):
"""調(diào)整列表中的元素以保證以index為根的堆是一個最大堆"""
# 將當(dāng)前結(jié)點與其左右子節(jié)點比較，將較大的結(jié)點與當(dāng)前結(jié)點交換，然后遞歸地調(diào)整子樹
left_child = 2 * index + 1
right_child = left_child + 1
if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]:
largest = left_child
else:
largest = index
if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]:
largest = right_child
if largest != index:
to_adjust_list[index], to_adjust_list[largest] = \
to_adjust_list[largest], to_adjust_list[index]
max_heap(to_adjust_list, heap_size, largest)
def heap_sort(to_sort_list):
"""堆排序"""
# 先將列表調(diào)整為堆
build_max_heap(to_sort_list)
heap_size = len(to_sort_list)
# 調(diào)整后列表的第一個元素就是這個列表中最大的元素，將其與最后一個元素交換，然后將剩余的列表再調(diào)整為最大堆
for i in range(len(to_sort_list) - 1, 0, -1):
to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
heap_size -= 1
max_heap(to_sort_list, heap_size, 0)
if __name__ == '__main__':
to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heap_sort(to_sort_list)
print to_sort_list
更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python正則表達(dá)式用法總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
在自然語言處理上，文字、音頻互轉(zhuǎn)是一個很關(guān)鍵的技術(shù)點。對于語音轉(zhuǎn)文字，個人實現(xiàn)較為困難，我們可以使用語音轉(zhuǎn)文字的軟件或借助各API（如科大訊飛等）進(jìn)行移植開發(fā)。不過文字轉(zhuǎn)語音就相對而言容易實現(xiàn)很多了2022-02-02
今天小編就為大家分享一篇pytorch常見的Tensor類型詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01
靈活運用Python 枚舉類來實現(xiàn)設(shè)計狀態(tài)碼信息
在python中枚舉是一種類（Enum,IntEnum），存放在enum模塊中。枚舉類型可以給一組標(biāo)簽賦予一組特定的值，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了如何在Win10中安裝dlib GPU，文中有非常詳細(xì)的圖文示例,對想要安裝dlib的小伙伴們很有幫助,需要的朋友可以參考下2021-12-12
Python使用matplotlib填充圖形指定區(qū)域代碼示例
這篇文章主要介紹了Python使用matplotlib填充圖形指定區(qū)域代碼示例，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
pydub是一個輕量級的音頻處理庫,安裝方便,使用簡單,這篇文章主要為大家詳細(xì)介紹了pydub的具體使用,文中的示例代碼講解詳細(xì),需要的小伙伴可以參考下2023-11-11
這篇文章主要介紹了PyQt5 matplotlib畫圖不刷新的解決方案，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
python3對拉勾數(shù)據(jù)進(jìn)行可視化分析的方法詳解
這篇文章主要給大家介紹了關(guān)于python3對拉勾數(shù)據(jù)進(jìn)行可視化分析的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Python3具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
這篇文章主要介紹了Python使用20行代碼實現(xiàn)微信聊天機器人,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-06-06
這篇文章主要給大家介紹了關(guān)于Django異步任務(wù)之Celery使用的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Django具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03