快捷導(dǎo)航

Python中的heapq模塊解析

更新時間：2023年09月13日 10:48:10 作者：Yake1965

這篇文章主要介紹了Python中的heapq模塊解析,heapq模塊是Python標準庫中的一個模塊,用于實現(xiàn)堆隊列(heapq)數(shù)據(jù)結(jié)構(gòu),它提供了一種方便的方式來實現(xiàn)堆排序等算法,需要的朋友可以參考下

heapq堆隊列算法

這個模塊提供了堆隊列算法的實現(xiàn)，也稱為優(yōu)先隊列算法。

堆是一個二叉樹，每個父節(jié)點的值 ≤ \le ≤ 所有孩子節(jié)點的值。用數(shù)組實現(xiàn)：從零開始計數(shù)，對于所有的 k ，都有 heap[k] ≤ \le ≤ heap[2k+1] 和 heap[k] ≤ \le ≤ heap[2k+2]。最小的元素總是在根結(jié)點：heap[0]。

heapq.heapify(x) # 將list x 轉(zhuǎn)換成堆，原地，線性時間內(nèi)。
heapq.heappush(heap, item) # 將 item 的值加入 heap 中，保持堆的不變性。
heapq.heappop(heap) 
#彈出并返回 heap 的最小的元素，保持堆的不變性。如果堆為空，拋出 IndexError 。使用 heap[0] ，可以只訪問最小的元素而不彈出它。
heapq.heappushpop(heap, item) 
#將 item 放入堆中，然后彈出并返回 heap 的最小元素。該組合操作比先調(diào)用 heappush() 再調(diào)用 heappop() 運行起來更有效率。
heapq.heapreplace(heap, item) 
#彈出并返回 heap 中最小的一項，同時推入新的 item。堆的大小不變。如果堆為空則引發(fā) IndexError。

這個單步驟操作比 heappop() 加 heappush() 更高效，并且在使用固定大小的堆時更為適宜。 pop/push 組合總是會從堆中返回一個元素并將其替換為 item。

返回的值可能會比添加的 item 更大。如果不希望如此，可考慮改用 heappushpop()。它的 push/pop 組合會返回兩個值中較小的一個，將較大的值留在堆中。

該模塊還提供了三個基于堆的通用功能函數(shù)。

heapq.merge(*iterables, key=None, reverse=False)
#將多個已排序的輸入合并為一個已排序的輸出（例如，合并來自多個日志文件的帶時間戳的條目）。 返回已排序值的 iterator。

類似于 sorted(itertools.chain(*iterables)) 但返回一個可迭代對象，不會一次性地將數(shù)據(jù)全部放入內(nèi)存，并假定每個輸入流都是已排序的（從小到大）。

具有兩個可選參數(shù)，它們都必須指定為關(guān)鍵字參數(shù)。

key 指定帶有單個參數(shù)的 key function，用于從每個輸入元素中提取比較鍵。默認值為 None (直接比較元素)。

reverse 為一個布爾值。如果設(shè)為 True，則輸入元素將按比較結(jié)果逆序進行合并。要達成與 sorted(itertools.chain(*iterables), reverse=True) 類似的行為，所有可迭代對象必須是已從大到小排序的。

heapq.nlargest(n, iterable, key=None)
#從 iterable 所定義的數(shù)據(jù)集中返回前 n 個最大元素組成的列表。 如果提供了 key 則其應(yīng)指定一個單參數(shù)的函數(shù)，用于從 iterable 的每個元素中提取比較鍵 (例如 key=str.lower)。 等價于: sorted(iterable, key=key, reverse=True)[:n]。
heapq.nsmallest(n, iterable, key=None)
#從 iterable 所定義的數(shù)據(jù)集中返回前 n 個最小元素組成的列表。 如果提供了 key 則其應(yīng)指定一個單參數(shù)的函數(shù)，用于從 iterable 的每個元素中提取比較鍵 (例如 key=str.lower)。 等價于: sorted(iterable, key=key)[:n]。

后兩個函數(shù)在 n 值較小時性能最好。對于更大的值，使用 sorted() 函數(shù)會更有效率。此外，當(dāng) n==1 時，使用內(nèi)置的 min() 和 max() 函數(shù)會更有效率。如果需要重復(fù)使用這些函數(shù)，請考慮將可迭代對象轉(zhuǎn)為真正的堆。

一、heapq 創(chuàng)建堆

import heapq 
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
    heapq.heappush(heap, num)
print("array:", array)
print("heap: ", heap)
heapq.heapify(array)
print("array:", array)
# array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
# heap:  [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
# array: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]

heapq 中創(chuàng)建堆的方法有兩種：

heappush(heap, num)，先創(chuàng)建一個空堆，然后將數(shù)據(jù)一個一個地添加到堆中。
heapify(array)，直接將數(shù)據(jù)列表調(diào)整成一個小頂堆。

二、堆排序

可以通過將所有值推入堆中然后每次彈出一個最小值項來實現(xiàn)。

def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]
heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

這類似于 sorted(iterable)，但與 sorted() 不同的是這個實現(xiàn)是不穩(wěn)定的。

堆元素可以為元組。這適用于將比較值（例如任務(wù)優(yōu)先級）與跟蹤的主記錄進行賦值的場合：

 h = []
 heappush(h, (5, 'write code'))
 heappush(h, (7, 'release product'))
 heappush(h, (1, 'write spec'))
 heappush(h, (3, 'create tests'))
 heappop(h)
(1, 'write spec')

先將待排序列表中的數(shù)據(jù)添加到堆中，構(gòu)造一個小頂堆，打印第一個數(shù)據(jù)，可以確認它是最小值。然后依次將堆頂?shù)闹等〕?，添加到一個新的列表中，直到堆中的數(shù)據(jù)取完，新列表就是排序后的列表。

heappop(heap)，將堆頂?shù)臄?shù)據(jù)出堆，并將堆中剩余的數(shù)據(jù)構(gòu)造成新的小頂堆。

三、獲取堆中的最小值或最大值

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heapq.heapify(array)
print(heapq.nlargest(2, array))
print(heapq.nsmallest(3, array))

四、使用heapq合并兩個有序列表

array_a = [10, 7, 15, 8]
array_b = [17, 3, 8, 20, 13]
array_merge = heapq.merge(sorted(array_a), sorted(array_b))
print("merge result:", list(array_merge))

五、heapq 替換數(shù)據(jù)的方法

array_c = [10, 7, 15, 8]
heapq.heapify(array_c)
print("before:", array_c)
# 先 push 再 pop
item = heapq.heappushpop(array_c, 5)
print("after: ", array_c)
print(item)
array_d = [10, 7, 15, 8]
heapq.heapify(array_d)
print("before:", array_d)
# 先 pop 再 push
item = heapq.heapreplace(array_d, 5)
print("after: ", array_d)
print(item)

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

您可能感興趣的文章: