Python标准库模块之heapq – 堆构造

堆作为优先队列的常用方法,而且在数据结构和算法方面,经常使用大顶堆和小顶堆进行问题的解决。

使用 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条)