heapq 是 python 的內建模組,原始碼位於 Lib/heapq.py ,該模組提供了基於堆疊的優先排序演算法。
堆的邏輯結構就是完全二元樹,而二元樹中父節點的值小於等於該節點的所有子節點的值。這種實作可以使用heap[k] <= heap[2k+1] 並且heap[k] <= heap[2k+2] (其中k 為索引,從0 開始計數)的形式體現,對堆來說,最小元素即為根元素heap[0]。
可以透過list 對heap 進行初始化,或透過api# 中的heapify 將已知的list 轉換為heap 物件。
heapq 提供的函數方法
#heapq.heappush(heap, item)
heapq.heappop(heap):傳回root 節點,即heap 中最小的元素
heapq.heappushpop(heap, item):向heap 中加入item 元素,並傳回heap 中最小元素
heapq.heapify(x)
heapq.nlargest(n, iterable, key=None):傳回可列舉物件中的n 個最大值,並傳回一個結果集list,key 為對該結果集的操作
heapq.nsmallest(n, iterable, key=None):同上相反
##demo
# 1. 透過heapq api 對list 進行排序def heapsort(iterable): h = [] for i in iterable: heapq.heappush(h, i) return [heapq.heappop(h) for i in range(len(h))] s = [3, 5, 1, 2, 4, 6, 0, 1] print(heapsort(s))
#
[0, 1, 1, 2, 3, 4, 5, 6]
portfolio = [ {'name': 'IBM', 'shares': 100, 'price': 91.1}, {'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}, {'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'ACME', 'shares': 75, 'price': 115.65} ] cheap = heapq.nsmallest(1, portfolio, key=lambda s: s['price']) print(cheap)
[{'shares': 45, 'price': 16.35, 'name': 'YHOO'}]
while 循環可以將較小的元素向上推
def heapilize_list(x): n = len(x) # 获取存在子节点的节点 index 列表,并对每个节点单元进行最小堆处理 for i in reversed(range(n // 2)): raiseup_node(x, i) def put_down_node(heap, startpos, pos): current_item = heap[pos] # 判断单元中最小子节点与父节点的大小 while pos > startpos: parent_pos = (pos - 1) >> 1 parent_item = heap[parent_pos] if current_item < parent_item: heap[pos] = parent_item pos = parent_pos continue break heap[pos] = current_item def raiseup_node(heap, pos): heap_len = len(heap) start_pos = pos current_item = heap[pos] left_child_pos = pos * 2 + 1 while left_child_pos < heap_len: right_child_pos = left_child_pos + 1 # 将这个单元中的最小子节点元素与父节点元素进行位置调换 if right_child_pos < heap_len and not heap[left_child_pos] < heap[right_child_pos]: left_child_pos = right_child_pos heap[pos] = heap[left_child_pos] pos = left_child_pos left_child_pos = pos * 2 + 1 heap[pos] = current_item put_down_node(heap, start_pos, pos) p = [4, 6, 2, 10, 1] heapilize_list(p) print(p)
#
[1, 6, 2, 10, 4]
以上是深入了解Python之heapq內建模組介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!