python中heapq堆排算法的實現(xiàn)

更新時間：2022年05月13日 17:17:39 作者：wx59129d39de499

這篇文章主要介紹了python中heapq堆排算法的實現(xiàn)，該模塊提供了堆排序算法的實現(xiàn)。堆是二叉樹，最大堆中父節(jié)點大于或等于兩個子節(jié)點，最小堆父節(jié)點小于或等于兩個子節(jié)點。下面文章更多詳細介紹，需要的小伙伴可以參考一下

一、創(chuàng)建堆

heapq有兩種方式創(chuàng)建堆，一種是使用一個空列表，然后使用heapq.heappush()函數(shù)把值加入堆中，另外一種就是使用heap.heapify(list)轉換列表成為堆結構

import heapq
# 第一種
"""
函數(shù)定義：
heapq.heappush(heap, item)
- Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(heap)
- Pop and return the smallest item from the heap, maintaining the heap invariant.
If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
"""
nums = [2, 3, 5, 1, 54, 23, 132]
heap = []
for num in nums:
heapq.heappush(heap, num) # 加入堆
print(heap[0]) # 如果只是想獲取最小值而不是彈出，使用heap[0]
print([heapq.heappop(heap) for _ in range(len(nums))]) # 堆排序結果
# out: [1, 2, 3, 5, 23, 54, 132]
# 第二種
nums = [2, 3, 5, 1, 54, 23, 132]
heapq.heapify(nums)
print([heapq.heappop(heap) for _ in range(len(nums))]) # 堆排序結果
# out: [1, 2, 3, 5, 23, 54, 132]

heapq 模塊還有一個??heapq.merge(*iterables)?? 方法，用于合并多個排序后的序列成一個排序后的序列，返回排序后的值的迭代器。

類似于??sorted(itertools.chain(*iterables))??，但返回的是可迭代的。

"""
函數(shù)定義：
heapq.merge(*iterables)
- Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an
iterator over the sorted values.
- Similar to sorted(itertools.chain(*iterables)) but returns an iterable, does not pull the data into memory all at once, and assumes
that each of the input streams is already sorted (smallest to largest).
"""
import heapq
num1 = [32, 3, 5, 34, 54, 23, 132]
num2 = [23, 2, 12, 656, 324, 23, 54]
num1 = sorted(num1)
num2 = sorted(num2)

res = heapq.merge(num1, num2)
print(list(res))

二、訪問堆內容

堆創(chuàng)建好后，可以通過`heapq.heappop() 函數(shù)彈出堆中最小值。

import heapq
nums = [2, 43, 45, 23, 12]
heapq.heapify(nums)
print(heapq.heappop(nums))
# out: 2
# 如果需要所有堆排序后的元素
result = [heapq.heappop(nums) for _ in range(len(nums))]
print(result)
# out: [12, 23, 43, 45]

如果需要刪除堆中最小元素并加入一個元素，可以使用??heapq.heaprepalce()?? 函數(shù)

import heapq
nums = [1, 2, 4, 5, 3]
heapq.heapify(nums)
heapq.heapreplace(nums, 23)
print([heapq.heappop(nums) for _ in range(len(nums))])
# out: [2, 3, 4, 5, 23]

三、獲取堆最大或最小值

如果需要獲取堆中最大或最小的范圍值，則可以使用??heapq.nlargest()??? 或??heapq.nsmallest()?? 函數(shù)

"""
函數(shù)定義：
heapq.nlargest(n, iterable[, key])?
- Return a list with the n largest elements from the dataset defined by iterable.
- key if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: key=str.lower
- Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
"""
import heapq

nums = [1, 3, 4, 5, 2]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

"""
輸出：
[5, 4, 3]
[1, 2, 3]
"""

這兩個函數(shù)還接受一個key參數(shù)，用于dict或其他數(shù)據(jù)結構類型使用

import heapq
from pprint import pprint
portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
pprint(cheap)
pprint(expensive)

"""
輸出：
[{'name': 'YHOO', 'price': 16.35, 'shares': 45},
{'name': 'FB', 'price': 21.09, 'shares': 200},
{'name': 'HPQ', 'price': 31.75, 'shares': 35}]
[{'name': 'AAPL', 'price': 543.22, 'shares': 50},
{'name': 'ACME', 'price': 115.65, 'shares': 75},
{'name': 'IBM', 'price': 91.1, 'shares': 100}]
"""

四、heapq應用

實現(xiàn)heap堆排序算法：

>>> def heapsort(iterable):
... h = []
... for value in iterable:
... heappush(h, value)
... return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

該算法和??sorted(iterable)?? 類似，但是它是不穩(wěn)定的。

堆的值可以是元組類型，可以實現(xiàn)對帶權值的元素進行排序。

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

到此這篇關于python中heapq堆排算法的實現(xiàn)的文章就介紹到這了,更多相關python heapq 堆內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: