Python标准库模块之heapq – 堆构造
读前福利:几百本经典书籍https://www.johngo689.com/2158/
原文链接:https://www.johngo689.com/2264/
堆作为优先队列的常用方法,而且在数据结构和算法方面,经常使用大顶堆和小顶堆进行问题的解决。
使用 Python 提供的标准库
heapq
:
import heapq
注意:默认的堆结构是小顶堆
一、构造堆 & 获取最小值
方法一:创建空列表,然后手动加入元素
heapq.heappush()
举例:
>>> nums = [2, 5, 1, 6, 9, 0]>>> heap = []>>> for num in nums:... heapq.heappush(heap, num)...>>> print(heap[0])0>>> print([heapq.heappop(heap) for _ in range(len(nums))])[0, 1, 2, 5, 6, 9]
方法二:初始化 list,然后转为堆结构
heapq.heapify(list)
直接将 list 转为堆结构
举例:
>>> nums = [2, 5, 1, 6, 9, 0]>>> # 转为heap结构...>>> heap.heapify(nums)>>> print(nums[0])0>>> print([heapq.heappop(nums) for _ in range(len(nums))])[0, 1, 2, 5, 6, 9]
删除最小值 并且 加入新元素, 使用
heapq.heaprepalce()
>>> nums = [2, 5, 1, 6, 9, 0]>>> # 转为heap结构...>>> heap.heapify(nums)>>> heapq.heapreplace(nums, 100)0>>> heapq.heapreplace(nums, -1)1>>> print([heapq.heappop(nums) for _ in range(len(nums))])[-1, 2, 5, 6, 9, 100]
二、获取最大值
这里没有直接构造大顶堆的方法,可以使用一个很巧妙的思路进行解决。
这是一个很 Tirck 的思路:
首先我们用上述方法一进行构造堆结构,注意要在每一个元素增加一个负号(-):
>>> nums[0, 5, 1, 6, 9, 2]>>> nums = [2, 5, 1, 6, 9, 0]>>> heap = []>>> for num in nums:... heapq.heappush(heap, -num)>>> heap[-9, -6, -1, -2, -5, 0]
接下来,打印堆元素,注意也要加负号(-):
>>> print([-heapq.heappop(heap) for _ in range(len(nums))])[9, 6, 5, 2, 1, 0]
这样是不是就巧妙的将大顶堆进行打印出来了。
整体思路:push(-) -> pop(-),负负得正。
三、获取最小值和最大值的范围
获取堆中最大或最小的范围值。
使用
heapq.nlargest()
或
heapq.nsmallest()
函数进行求得:
>>> nums = [2, 5, 1, 6, 9, 0]>>> heapq.heapify(nums)>>> heapq.nlargest(3, nums)[9, 6, 5]>>> heapq.nsmallest(3, nums)[0, 1, 2]
这个比较简单,需要主要添加范围值。