python內建堆如何實現-Python教學-PHP中文網

1.簡介

#堆，又稱為優先隊列，是完全二元樹，它的每個父節點的值只會小於或等於所有孩子節點（的值）。它使用了數組來實現：從零開始計數，對於所有的k ，都有 heap[k] 。為了便於比較，不存在的元素被認為是無限大。堆最有趣的特性在於最小的元素總是根結點：heap[0]。

python的堆一般都是最小堆，與許多教材上的內容有所不同，教材上大多以最大堆，由於堆的表示方法，從上到下，從左到右存儲，與列表十分相似，因此創建一個堆，可以使用list來初始化為[] ，或者你可以透過一個函數heapify() ，來把一個list轉換成堆。如下是python中關於堆的相關操作，從這可以看出，python確實是將堆看作是列表去處理的。

python內建堆如何實現

2.堆的相關操作

heapq.heappush(heap, item)

將item 的值加入heap 中，保持堆的不變性。會自動依據python中的最小堆特性，交換相關元素使得堆的根節點元素始終不大於子節點元素。

原有資料是堆

import heapq

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

登入後複製

操作流程如下:

1.如下是初始狀態

python內建堆如何實現

2.加入了2元素之後

python內建堆如何實現

#3.由於不符合最小堆的特性，因此與3交換

python內建堆如何實現

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

原有資料不是堆

import heapq

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

登入後複製

由此可見，當進行push操作時，元素不是堆的情況下，預設會依照列表的append方法進行新增元素

heapq.heappop( heap)

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

原有資料是堆疊

import heapq

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

登入後複製

操作流程如下：

1.初始狀態

python內建堆如何實現

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

python內建堆如何實現

#3.依據python最小堆的特性進行交換元素，由於7>2，交換7和2

python內建堆如何實現

4.依據python最小堆的特性進行交換元素，由於7>5，交換7和5

python內建堆如何實現

#5.符合堆的要求，即結果為[2, 5, 3, 7]

原有資料不是堆

import heapq

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

[1, 2, 7, 4]

登入後複製

操作流程如下：

1.初始狀態，很明顯不符合堆的性質

python內建堆如何實現

##2.移除最上面的元素（第一個元素）,重新對剩下的元素進行堆的排列

python內建堆如何實現

#3.依據python最小堆的特性，2>1 交換2與1

python內建堆如何實現

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

heapq.heappushpop(heap, item)

將item 放入堆中，然後彈出並返回heap 的最小元素。這個組合運算比先呼叫 heappush() 再呼叫 heappop() 運作起來更有效率。要注意的是彈出的元素必須位於堆頂或堆尾，也就是說當插入一個元素後，進行比較最小元素時，其實一直比較的都是堆頂元素，如果插入元素大於或等於堆頂元素，則堆不會發生變化，當插入元素小於堆頂元素，則堆會依據python堆的最小堆特性進行處理。

原有資料是堆

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.初始狀態

python內建堆如何實現

#2.插入元素2

python內建堆如何實現

###

3.删除最小元素，刚好是堆顶元素1，并使用末尾元素2代替

python內建堆如何實現

4.符合要求，即结果为[2, 2, 3, 5, 7]

原有数据不是堆

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]

登入後複製

对于插入元素6的操作过程如下

1.初始状态

python內建堆如何實現

2.插入元素6之后

python內建堆如何實現

3.发现元素6大于堆顶元素5，弹出堆顶元素5，由堆尾元素6替换

python內建堆如何實現

4.依据python的最小堆特性，元素6>元素1且元素6>元素2，但元素2>元素1，交换6与1

python內建堆如何實現

5.符合要求，则结果为[1, 2, 6, 4, 7]

由结果可以看出，当插入元素小于堆顶元素时，则堆不会发生改变，当插入元素大于堆顶元素时，则堆依据python堆的最小堆特性处理。

heapq.heapify(x)

将列表转换为堆。

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]

登入後複製

会自动将列表依据python最小堆特性进行重新排列。

heapq.heapreplace(heap, item)

弹出并返回最小的元素，并且添加一个新元素item，这个单步骤操作比heappop()加heappush() 更高效。适用于堆元素数量固定的情况。

返回的值可能会比添加的 item 更大。如果不希望如此，可考虑改用heappushpop()。它的 push/pop 组合会返回两个值中较小的一个，将较大的值留在堆中。

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]

登入後複製

原有数据是堆

对于插入元素6的操作过程如下：

1.初始状态

python內建堆如何實現

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

python內建堆如何實現

3.依据python堆的最小堆特性，6>2,交换6与2

python內建堆如何實現

4.依据python堆的最小堆特性，6>5,交换6与5

python內建堆如何實現

5.符合要求，则结果为[2, 5, 3, 6 ,7]

原有数据不是堆

对于插入元素6的操作过程如下：

1.初始状态

python內建堆如何實現

2.对于数据不为堆的情况下，默认移除第一个元素，这里就是元素5，然后插入元素6到堆顶

python內建堆如何實現

3.依据python的最小堆特性，元素6>1,交换元素6与1

python內建堆如何實現

4.符合要求，即结果为[1, 2, 6, 4, 7

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

将多个已排序的输入合并为一个已排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。返回已排序值的 iterator。注意需要是已排序完成的可迭代对象（默认为从小到大排序），当reverse为True时，则为从大到小排序。

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

从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。

等价于: 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]

登入後複製

由上述结构可见，heapq.nlargest与sorted(iterable, key=key, reverse=False)[:n]功能是类似的，但是性能方面还是sorted较为快速。

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

从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。等价于: 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

登入後複製

由上述结果可见，sorted的性能比后面两个函数都要好，但如果只是返回最大的或者最小的一个元素，则使用max和min最好。

3.堆排序

由于在python中堆的特性是最小堆，堆顶的元素始终是最小的，可以将序列转换成堆之后，再使用pop弹出堆顶元素来实现从小到大排序。具体实现如下：

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.堆中元素可以是元组形式，主要用于任务优先级

from heapq import heappush, heappop

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

[(1, &#39;write spec&#39;), (3, &#39;create tests&#39;), (5, &#39;write code&#39;), (7, &#39;release product&#39;)]
(1, &#39;write spec&#39;)

登入後複製

上述操作流程如下：

1.当进行第一次push(5, ‘write code’)时

python內建堆如何實現