下面小編就為大家帶來一篇python下實作二元堆以及堆排序的範例。小編覺得蠻不錯的，現在就分享給大家，也給大家做個參考。一起跟著小編過來看看吧
堆是一種特殊的樹狀結構， 堆中的資料儲存滿足一定的堆序。堆排序是一種選擇排序， 其演算法複雜度， 時間複雜度相對於其他的排序演算法都有很大的優勢。
堆分為大頭堆和小頭堆， 如其名， 大頭堆的第一個元素是最大的， 每個有子結點的父結點， 其數據值都比其子結點的值要大。小頭堆則相反。
我大概講解下建一個樹狀堆的演算法過程:
找到N/2 位置的陣列數據， 從這個位置開始， 找出該節點的左子結點的索引， 先比較這個結點的下的子結點， 找到最大的那個， 將最大的子結點的索引賦值給左子結點， 然後將最大的子結點和父結點進行對比， 如果比父結點大， 與父節點交換資料。當然， 我只是大概說了下實現， 在此過程中， 還需要考慮結點不存在的情況。
看下程式碼：
# 构建二叉堆
def binaryHeap(arr, lenth, m):
temp = arr[m] # 当前结点的值
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp
def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1
print("二叉堆的物理顺序为:")
print(arr) # 输出二叉堆的物理顺序
if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]
heapsort(arr, len(arr))堆排序過程就是依序將最後的結點與首個節點進行對比交換：
# 构建二叉堆
def binaryHeap(arr, lenth, m):
temp = arr[m] # 当前结点的值
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp
def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1
print("二叉堆的物理顺序为:")
print(arr) # 输出二叉堆的物理顺序
i = length-1
while(i > 0):
arr[i], arr[0] = arr[0], arr[i] # 变量交换
binaryHeap(arr, i, 0)
i = i - 1560
def pop(arr):
first = arr.pop(0)
return first
if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]
heapsort(arr, len(arr))
print("堆排序后的物理顺序")
print(arr) # 输出经过堆排序之后的物理顺序
data = pop(arr)
print(data)
print(arr)python封裝了一個堆疊模組, 我們使用該模組可以很有效率的實作一個優先隊列
##
import heapq
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一个三元组
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1] # 逆序输出
if __name__ == '__main__':
p = PriorityQueue()
p.push(Item('foo'), 1)
p.push(Item('bar'), 5)
p.push(Item('spam'), 4)
p.push(Item('grok'), 1)
print(p.pop())
print(p.pop())以上是python實作二元堆與堆排序的程式碼實例的詳細內容。更多資訊請關注PHP中文網其他相關文章！
