Python - heapq 模組介紹
在 Python 中,有一個內建的 heapq 模組提供了最小堆積的函數。
在本文中,我們將會介紹 heapq 模組的用法。
heapq.heappush() 與 heapq.heappop()
heapq.heappush()
函數可以用來將元素加入到最小堆積中,而 heapq.heappop()
函數則是將最小堆積中的最小元素取出。
其中 heapq.heapify(x)
可以在線性時間 O(n)
時間內將 data 轉為 heap,且過程不會申請額外記憶體。
1 | import heapq |
heapq.heappushpop() 與 heapq.heapreplace()
heapq.heappushpop()
函數可以用來將元素加入到最小堆積中,並且取出最小元素。因此這個組合函式比呼叫 heappush()
之後呼叫 heappop()
更有效率。
1 | import heapq |
heapq.heapreplace()
函數則是將最小堆積中的最小元素取出,並且加入新的元素。因此這個組合函式比呼叫 heappop()
之後呼叫 heappush()
更有效率。
1 | import heapq |
heapq.nlargest() 與 heapq.nsmallest()
heapq.nlargest()
函數可以用來取出最大的 n 個元素,而 heapq.nsmallest()
函數則是取出最小的 n 個元素。
1 | import heapq |
heapq.merge()
heapq.merge()
函數可以用來將多個已排序的 iterable 合併成一個已排序的 iterable。
1 | import heapq |
結論
heapq 模組提供了最小堆積的函數,可以讓我們在 Python 中更方便地使用最小堆積。
你可以在官方文件中找到更多 heapq 模組的函數,heapq — Heap queue algorithm。
也可以直接閱讀他的原始碼,heapq.py。
☺️