堆作为优先队列的常用方法，而且在数据结构和算法方面，经常使用大顶堆和小顶堆进行问题的解决。
使用 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]
这个比较简单，需要主要添加范围值。
发布者：Johngo学长。文章已受到原创版权保护。
转载请注明出处：https://www.johngo689.com/2264/
微信扫一扫 
支付宝扫一扫 
评论列表（1条）
[…] 原文链接：https://www.johngo689.com/2264/ […]