Python heapq

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

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

堆結(jié)構(gòu)分為大頂堆和小頂堆，在 heapq 中使用的是小頂堆：

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

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

使用Python實現(xiàn)堆排序可以參考：http://www.dbjr.com.cn/article/222484.htm

完全二叉樹的特性可以參考：http://www.dbjr.com.cn/article/222487.htm

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

運行結(jié)果：

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ù)一個一個地添加到堆中。每添加一個數(shù)據(jù)后，heap 都滿足小頂堆的特性。

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

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

使用heapify(array)得到的堆結(jié)構(gòu)如下。

不過，這兩個結(jié)果都滿足小頂堆的特性，不影響堆的使用(堆只會從堆頂開始取數(shù)據(jù)，取出數(shù)據(jù)后會重新調(diào)整結(jié)構(gòu))。

二、使用 heapq 實現(xiàn)堆排序

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)

運行結(jié)果：

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

先將待排序列表中的數(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))

運行結(jié)果：

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

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

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

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

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

運行結(jié)果：

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

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

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

運行結(jié)果：

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 添加到堆中，然后將堆頂?shù)臄?shù)據(jù)出堆。
heapreplace(heap, num)，先將堆頂?shù)臄?shù)據(jù)出堆，然后將 num 添加到堆中。

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

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

最新評論