快捷導(dǎo)航

Python heapq庫(kù)案例詳解

更新時(shí)間：2021年09月10日 09:02:29 作者：Yake1965

這篇文章主要介紹了Python heapq庫(kù)案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

Python heapq

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

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

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

大頂堆：每個(gè)節(jié)點(diǎn)(葉節(jié)點(diǎn)除外)的值都大于等于其子節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值是所有節(jié)點(diǎn)中最大的。
小頂堆：每個(gè)節(jié)點(diǎn)(葉節(jié)點(diǎn)除外)的值都小于等于其子節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值是所有節(jié)點(diǎn)中最小的。

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

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

完全二叉樹(shù)的特性可以參考：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)

運(yùn)行結(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)建一個(gè)空堆，然后將數(shù)據(jù)一個(gè)一個(gè)地添加到堆中。每添加一個(gè)數(shù)據(jù)后，heap 都滿(mǎn)足小頂堆的特性。

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

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

在這里插入圖片描述

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

在這里插入圖片描述

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

二、使用 heapq 實(shí)現(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)

運(yùn)行結(jié)果：

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

先將待排序列表中的數(shù)據(jù)添加到堆中，構(gòu)造一個(gè)小頂堆，打印第一個(gè)數(shù)據(jù)，可以確認(rèn)它是最小值。然后依次將堆頂?shù)闹等〕?，添加到一個(gè)新的列表中，直到堆中的數(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))

運(yùn)行結(jié)果：

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

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

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

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

四、使用heapq合并兩個(gè)有序列表

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

運(yùn)行結(jié)果：

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

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

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

運(yùn)行結(jié)果：