Python heapq

heapq 庫是 Python 標準庫之一，提供了構建小頂堆的方法和一些對小頂堆的基本操作方法(如入堆，出堆等)，可以用于實現堆排序算法。

堆是一種基本的數據結構，堆的結構是一棵完全二叉樹，并且滿足堆積的性質：每個節點(葉節點除外)的值都大于等于(或都小于等于)它的子節點。

堆結構分為大頂堆和小頂堆，在 heapq 中使用的是小頂堆：

1. 大頂堆：每個節點(葉節點除外)的值都大于等于其子節點的值，根節點的值是所有節點中最大的。
2. 小頂堆：每個節點(葉節點除外)的值都小于等于其子節點的值，根節點的值是所有節點中最小的。

在 heapq 庫中，heapq 使用的數據類型是 Python 的基本數據類型 list ，要滿足堆積的性質，則在這個列表中，索引 k 的值要小于等于索引 2k+1 的值和索引 2k+2 的值（在完全二叉樹中，將數據按廣度優先插入，索引為k的節點的子節點索引分別為 2k+1 和 2k+2）。在 heapq 庫的源碼中也有介紹，可以讀一下 heapq 的源碼，代碼不多。

使用Python實現堆排序可以參考：https://www.jb51.net/article/222484.htm

完全二叉樹的特性可以參考：https://www.jb51.net/article/222487.htm

一、使用 heapq 創建堆

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 中創建堆的方法有兩種：

heappush(heap, num)，先創建一個空堆，然后將數據一個一個地添加到堆中。每添加一個數據后，heap 都滿足小頂堆的特性。

heapify(array)，直接將數據列表調整成一個小頂堆（調整的原理參考上面堆排序的文章，heapq庫已經實現了）。

兩種方法實現的結果會有差異，如上面的代碼中，使用 heappush(heap, num) 得到的堆結構如下。

使用heapify(array)得到的堆結構如下。

不過，這兩個結果都滿足小頂堆的特性，不影響堆的使用(堆只會從堆頂開始取數據，取出數據后會重新調整結構)。

二、使用 heapq 實現堆排序

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
    heapq.heappush(heap, num)
print(heap[0])
# print(heapq.heappop(heap))
heap_sort = [heapq.heappop(heap) for _ in range(len(heap))]
print("heap sort result: ", heap_sort)

運行結果：

5
heap sort result:  [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

先將待排序列表中的數據添加到堆中，構造一個小頂堆，打印第一個數據，可以確認它是最小值。然后依次將堆頂的值取出，添加到一個新的列表中，直到堆中的數據取完，新列表就是排序后的列表。

heappop(heap)，將堆頂的數據出堆，并將堆中剩余的數據構造成新的小頂堆。

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

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))

運行結果：

[50, 45]
[5, 7, 10]

nlargest(num, heap)，從堆中取出 num 個數據，從最大的數據開始取，返回結果是一個列表(即使只取一個數據)。如果 num 大于等于堆中的數據數量，則從大到小取出堆中的所有數據，不會報錯，相當于實現了降序排序。

nsmallest(num, heap)，從堆中取出 num 個數據，從最小的數據開始取，返回結果是一個列表。

這兩個方法除了可以用于堆，也可以直接用于列表，功能一樣。

四、使用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))

運行結果：

merge result: [3, 7, 8, 8, 10, 13, 15, 17, 20]

merge(list1, list2)，將兩個有序的列表合并成一個新的有序列表，返回結果是一個迭代器。這個方法可以用于歸并排序。

五、heapq 替換數據的方法

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)

運行結果：

before: [7, 8, 15, 10]
after:  [7, 8, 15, 10]
5
before: [7, 8, 15, 10]
after:  [5, 8, 15, 10]
7

heappushpop(heap, num)，先將 num 添加到堆中，然后將堆頂的數據出堆。
heapreplace(heap, num)，先將堆頂的數據出堆，然后將 num 添加到堆中。

兩個方法都是即入堆又出堆，只是順序不一樣，可以用于替換堆中的數據。具體的區別可以看代碼中的例子。

到此這篇關于Python heapq庫案例詳解的文章就介紹到這了,更多相關Python heapq庫內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！