快捷導(dǎo)航

python內(nèi)置堆的具體實(shí)現(xiàn)

更新時(shí)間：2023年03月22日 10:35:13 作者：Python程序u猿

本文主要介紹了python內(nèi)置堆的具體實(shí)現(xiàn)，堆的表示方法，從上到下，從左到右存儲(chǔ)，與列表十分相似，本文就來介紹一下，感興趣的可以了解一下

1.簡(jiǎn)介

堆，又稱優(yōu)先隊(duì)列，是一個(gè)完全二叉樹，它的每個(gè)父節(jié)點(diǎn)的值都只會(huì)小于或等于所有孩子節(jié)點(diǎn)（的值）。它使用了數(shù)組來實(shí)現(xiàn)：從零開始計(jì)數(shù)，對(duì)于所有的 k ，都有 heap[k] <= heap[2k+1] 和 heap[k] <= heap[2k+2]。為了便于比較，不存在的元素被認(rèn)為是無限大。堆最有趣的特性在于最小的元素總是在根結(jié)點(diǎn)：heap[0]。

python的堆一般都是最小堆，與很多教材上的內(nèi)容有所不同，教材上大多以最大堆，由于堆的表示方法，從上到下，從左到右存儲(chǔ)，與列表十分相似，因此創(chuàng)建一個(gè)堆，可以使用list來初始化為 [] ，或者你可以通過一個(gè)函數(shù) heapify() ，來把一個(gè)list轉(zhuǎn)換成堆。如下是python中關(guān)于堆的相關(guān)操作，從這可以看出，python確實(shí)是將堆看作是列表去處理的。

在這里插入圖片描述

2.堆的相關(guān)操作

heapq.heappush(heap, item)

將 item 的值加入 heap 中，保持堆的不變性。會(huì)自動(dòng)依據(jù)python中的最小堆特性，交換相關(guān)元素使得堆的根節(jié)點(diǎn)元素始終不大于子節(jié)點(diǎn)元素。

原有數(shù)據(jù)是堆

import heapq

h = [1, 2, 3, 5, 7]
heapq.heappush(h, 2)
print(h)
#輸出
[1, 2, 2, 5, 7, 3]

操作流程如下:

1.如下是初始狀態(tài)

在這里插入圖片描述

2.添加了2元素之后

在這里插入圖片描述

3.由于不符合最小堆的特性，因此與3進(jìn)行交換

在這里插入圖片描述

4.符合最小堆的特性，交換結(jié)束，因此結(jié)果是[1, 2, 3, 5, 7, 3]

原有數(shù)據(jù)不是堆

import heapq

h = [5, 2, 1, 4, 7]
heapq.heappush(h, 2)
print(h)
#輸出
[5, 2, 1, 4, 7, 2]

由此可見，當(dāng)進(jìn)行push操作時(shí)，元素不是堆的情況下，默認(rèn)按照列表的append方法進(jìn)行添加元素

heapq.heappop(heap)

彈出并返回 heap 的最小的元素，保持堆的不變性。如果堆為空，拋出 IndexError 。使用 heap[0] ，可以只訪問最小的元素而不彈出它。

原有數(shù)據(jù)是堆

import heapq

h = [1, 2, 3, 5, 7]
heapq.heappop(h)
print(h)
#輸出
[2, 5, 3, 7]

操作流程如下：

1.初始狀態(tài)

在這里插入圖片描述

2.刪除了堆頂元素，末尾元素移入堆頂

在這里插入圖片描述

3.依據(jù)python最小堆的特性進(jìn)行交換元素，由于7>2，交換7和2

在這里插入圖片描述

4.依據(jù)python最小堆的特性進(jìn)行交換元素，由于7>5，交換7和5

在這里插入圖片描述

5.符合堆的要求，即結(jié)果為[2, 5, 3, 7]

原有數(shù)據(jù)不是堆

import heapq

h = [5, 2, 1, 4, 7]
heapq.heappop(h)
print(h)

[1, 2, 7, 4]

操作流程如下：

1.初始狀態(tài)，很明顯不符合堆的性質(zhì)

在這里插入圖片描述

2.移除最上面的元素（第一個(gè)元素）,重新對(duì)剩下的元素進(jìn)行堆的排列

在這里插入圖片描述

3.依據(jù)python最小堆的特性，2>1 交換2與1

在這里插入圖片描述

4.符合堆的要求，結(jié)果為[1, 2, 7, 4]

heapq.heappushpop(heap, item)

將 item 放入堆中，然后彈出并返回 heap 的最小元素。該組合操作比先調(diào)用 heappush() 再調(diào)用 heappop() 運(yùn)行起來更有效率。需要注意的是彈出的元素必須位于堆頂或者堆尾，也就是說當(dāng)插入一個(gè)元素后，進(jìn)行比較最小元素時(shí)，其實(shí)一直比較的都是堆頂元素，如果插入元素大于或等于堆頂元素，則堆不會(huì)發(fā)生變化，當(dāng)插入元素小于堆頂元素，則堆會(huì)依據(jù)python堆的最小堆特性進(jìn)行處理。

原有數(shù)據(jù)是堆

import heapq

h = [1, 2, 3, 5, 7]
min_data = heapq.heappushpop(h, 2)
print(min_data)
print(h)
#輸出
1
[2, 2, 3, 5, 7]

操作流程如下

1.初始狀態(tài)

在這里插入圖片描述

2.插入元素2

在這里插入圖片描述

3.刪除最小元素，剛好是堆頂元素1，并使用末尾元素2代替

在這里插入圖片描述

4.符合要求，即結(jié)果為[2, 2, 3, 5, 7]

原有數(shù)據(jù)不是堆

h = [5, 2, 1, 4, 7]
min_data = heapq.heappushpop(h, 2)
print(min_data)
print(h)
min_data = heapq.heappushpop(h, 6)
print(min_data)
print(h)

#輸出
2
[5, 2, 1, 4, 7]
5
[1, 2, 6, 4, 7]

對(duì)于插入元素6的操作過程如下

1.初始狀態(tài)

在這里插入圖片描述

2.插入元素6之后

在這里插入圖片描述

3.發(fā)現(xiàn)元素6大于堆頂元素5，彈出堆頂元素5，由堆尾元素6替換

在這里插入圖片描述

4.依據(jù)python的最小堆特性，元素6>元素1且元素6>元素2，但元素2>元素1，交換6與1

在這里插入圖片描述

5.符合要求，則結(jié)果為[1, 2, 6, 4, 7]

由結(jié)果可以看出，當(dāng)插入元素小于堆頂元素時(shí)，則堆不會(huì)發(fā)生改變，當(dāng)插入元素大于堆頂元素時(shí)，則堆依據(jù)python堆的最小堆特性處理。

heapq.heapify(x)

將列表轉(zhuǎn)換為堆。

h = [1, 2, 3, 5, 7]
heapq.heapify(h)
print(h)
h = [5, 2, 1, 4, 7]
heapq.heapify(h)
print(h)
#輸出
[1, 2, 3, 5, 7]
[1, 2, 5, 4, 7]

會(huì)自動(dòng)將列表依據(jù)python最小堆特性進(jìn)行重新排列。

heapq.heapreplace(heap, item)

彈出并返回最小的元素，并且添加一個(gè)新元素item，這個(gè)單步驟操作比heappop()加heappush() 更高效。適用于堆元素?cái)?shù)量固定的情況。

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

import heapq

h = [1, 2, 3, 5, 7]
heapq.heapreplace(h, 6)
print(h)
h = [5, 2, 1, 4, 7]
heapq.heapreplace(h, 6)
print(h)
#輸出
[2, 5, 3, 6, 7]
[1, 2, 6, 4, 7]

原有數(shù)據(jù)是堆

對(duì)于插入元素6的操作過程如下：

1.初始狀態(tài)

在這里插入圖片描述

2.彈出最小元素，只能彈出堆頂或者堆尾的元素，很明顯，最小元素是1，彈出1，插入元素是6，代替堆頂元素

在這里插入圖片描述

3.依據(jù)python堆的最小堆特性，6>2,交換6與2

在這里插入圖片描述

4.依據(jù)python堆的最小堆特性，6>5,交換6與5

在這里插入圖片描述

5.符合要求，則結(jié)果為[2, 5, 3, 6 ,7]

原有數(shù)據(jù)不是堆

對(duì)于插入元素6的操作過程如下：

1.初始狀態(tài)

在這里插入圖片描述

2.對(duì)于數(shù)據(jù)不為堆的情況下，默認(rèn)移除第一個(gè)元素，這里就是元素5，然后插入元素6到堆頂

在這里插入圖片描述

3.依據(jù)python的最小堆特性，元素6>1,交換元素6與1

在這里插入圖片描述

4.符合要求，即結(jié)果為[1, 2, 6, 4, 7

heapq.merge(*iterables, key=None, reverse=False)

將多個(gè)已排序的輸入合并為一個(gè)已排序的輸出（例如，合并來自多個(gè)日志文件的帶時(shí)間戳的條目）。返回已排序值的 iterator。注意需要是已排序完成的可迭代對(duì)象（默認(rèn)為從小到大排序），當(dāng)reverse為True時(shí)，則為從大到小排序。

heapq.nlargest(n, iterable, key=None)

從 iterable 所定義的數(shù)據(jù)集中返回前 n 個(gè)最大元素組成的列表。如果提供了 key 則其應(yīng)指定一個(gè)單參數(shù)的函數(shù)，用于從 iterable 的每個(gè)元素中提取比較鍵 (例如 key=str.lower)。

等價(jià)于: sorted(iterable, key=key, reverse=True)[:n]。

import time
import heapq

h = [1, 2, 3, 5, 7]

size = 1000000
start = time.time()
print(heapq.nlargest(3, h))
for i in range(size):
    heapq.nlargest(3, h)
print(time.time() - start)

start = time.time()
print(sorted(h, reverse=True)[:3:])
for i in range(size):
    sorted(h, reverse=True)[:3:]
print(time.time() - start)
#輸出
[7, 5, 3]
1.6576552391052246
[7, 5, 3]
0.2772986888885498
[7, 5, 4]

由上述結(jié)構(gòu)可見，heapq.nlargest與sorted(iterable, key=key, reverse=False)[:n]功能是類似的，但是性能方面還是sorted較為快速。

heapq.nsmallest(n, iterable, key=None)

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

import time
import heapq

h = [1, 2, 3, 5, 7]

size = 1000000
start = time.time()
print(heapq.nsmallest(3, h))
for i in range(size):
    heapq.nsmallest(2, h)
print(time.time() - start)

start = time.time()
print(sorted(h, reverse=False)[:3:])
for i in range(size):
    sorted(h, reverse=False)[:2:]
print(time.time() - start)
#輸出
[1, 2, 3]
1.1738648414611816
[1, 2, 3]
0.2871997356414795

由上述結(jié)果可見，sorted的性能比后面兩個(gè)函數(shù)都要好，但如果只是返回最大的或者最小的一個(gè)元素，則使用max和min最好。

3.堆排序

由于在python中堆的特性是最小堆，堆頂?shù)脑厥冀K是最小的，可以將序列轉(zhuǎn)換成堆之后，再使用pop彈出堆頂元素來實(shí)現(xiàn)從小到大排序。具體實(shí)現(xiàn)如下：

from heapq import heappush, heappop, heapify


def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]


def heapsort2(iterable):
    heapify(iterable)
    return [heappop(iterable) for i in range(len(iterable))]


data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]

print(heapsort(data))
print(heapsort2(data))
#輸出
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4.堆中元素可以是元組形式，主要用于任務(wù)優(yōu)先級(jí)

from heapq import heappush, heappop

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

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

上述操作流程如下：

1.當(dāng)進(jìn)行第一次push(5, ‘write code’)時(shí)

在這里插入圖片描述