python 堆排序的兩種實現(xiàn)

import heapq #-*- coding: UTF-8 -*- import numpy as npdef MakeHeap(a):for i in range(int(a.size / 2) - 1, -1, -1):#對非葉子節(jié)點的子節(jié)點進行調(diào)節(jié)，構(gòu)建堆AdjustHeap(a, i, a.size)def AdjustHeap(a, i, n):j = i*2 +1 #選擇節(jié)點i的左子節(jié)點x = a[i] #選擇節(jié)點的數(shù)值while j < n: #循環(huán)對子節(jié)點及其子樹進行調(diào)整if j + 1 < n and a[j+1] < a[j]: #找到節(jié)點i子節(jié)點的最小值j += 1if a[j] >= x : #若兩個子節(jié)點均不小于該節(jié)點，則不同調(diào)整breaka[i], a[j] = a[j], a[i] #將節(jié)點i的數(shù)值與其子節(jié)點中最小者的數(shù)值進行對調(diào)i = j #將i賦為改變的子節(jié)點的索引j = i*2 + 1 #將j賦為節(jié)點對應(yīng)的左子節(jié)點def HeapSort(a):MakeHeap(a) #構(gòu)建小頂堆for i in range(a.size - 1,0, -1): #對堆中的元素逆向遍歷a[i], a[0] = a[0], a[i] #將堆頂元素與堆中最后一個元素進行對調(diào)，因為小頂堆中堆頂元素永遠最小，因此，輸出即為最小元素AdjustHeap(a, 0, i) #重新調(diào)整使剩下的元素仍為一個堆if __name__ == '__main__':a = np.random.randint(0, 100, size = 10)print ("Before sorting...")print ("---------------------------------------------------------------")print (a)print ("---------------------------------------------------------------")a1=aHeapSort(a1)print ("After sorting...")print ("---------------------------------------------------------------")print (a1[::-1] ) #因為堆排序按大到小進行排列，采用a[::-1]對其按從小到大進行輸出print(a1)print( "---------------------------------------------------------------")b=list(a)heapq.heapify(b)heap = []while b:heap.append(heapq.heappop(b))b[:] = heapprint ('-------------------------------------------------')print ('sdk sorted',b) Before sorting... --------------------------------------------------------------- [92 97 3 60 8 67 13 65 35 94] --------------------------------------------------------------- After sorting... --------------------------------------------------------------- [ 3 8 13 35 60 65 67 92 94 97] [97 94 92 67 65 60 35 13 8 3] --------------------------------------------------------------- ------------------------------------------------- sdk sorted [3, 8, 13, 35, 60, 65, 67, 92, 94, 97]

posted on 2018-06-27 10:43 luoganttcc 閱讀(...) 評論(...) 編輯 收藏

總結(jié)

以上是生活随笔為你收集整理的python 堆排序的两种实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。