个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
29
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Python heapq使用详解及实例代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
Python heapq 详解 。
Python有一个内置的模块，heapq标准的封装了最小堆的算法实现。下面看两个不错的应用.
小顶堆（求TopK大） 。
话说需求是这样的： 定长的序列，求出TopK大的数据.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import
heapq
import
random
class
TopkHeap(
object
):
def
__init__(
self
, k):
self
.k
=
k
self
.data
=
[]
def
Push(
self
, elem):
if
len
(
self
.data) <
self
.k:
heapq.heappush(
self
.data, elem)
else
:
topk_small
=
self
.data[
0
]
if
elem > topk_small:
heapq.heapreplace(
self
.data, elem)
def
TopK(
self
):
return
[x
for
x
in
reversed
([heapq.heappop(
self
.data)
for
x
in
xrange
(
len
(
self
.data))])]
if
__name__
=
=
"__main__"
:
print
"Hello"
list_rand
=
random.sample(
xrange
(
1000000
),
100
)
th
=
TopkHeap(
3
)
for
i
in
list_rand:
th.Push(i)
print
th.TopK()
print
sorted
(list_rand, reverse
=
True
)[
0
:
3
]
|
大顶堆（求BtmK小） 。
这次的需求变得更加的困难了：给出N长的序列，求出BtmK小的元素，即使用大顶堆.
算法实现的核心思路是：将push(e)改为push(-e)、pop(e)改为-pop(e).
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class
BtmkHeap(
object
):
def
__init__(
self
, k):
self
.k
=
k
self
.data
=
[]
def
Push(
self
, elem):
# Reverse elem to convert to max-heap
elem
=
-
elem
# Using heap algorighem
if
len
(
self
.data) <
self
.k:
heapq.heappush(
self
.data, elem)
else
:
topk_small
=
self
.data[
0
]
if
elem > topk_small:
heapq.heapreplace(
self
.data, elem)
def
BtmK(
self
):
return
sorted
([
-
x
for
x
in
self
.data])
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ 。
最后此篇关于Python heapq使用详解及实例代码的文章就讲到这里了,如果你想了解更多关于Python heapq使用详解及实例代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
29
4
0
我注意到给定一个列表，如果我使用 heapq.heapify() 创建一个堆，元素的顺序与我在列表上迭代并执行 heap.heappush() 时获得的顺序不同。 谁能帮我理解为什么？ 此外，对于可迭
我正在尝试使用 Python 的 heapq 来实现 Dijkstra 的算法。如果发现通往它的较短路径，则该算法需要更改单元格的值。 我正在通过此检查执行此操作: if curr_cell[0] +
来自官方heapq的示例: >>> heap = [] >>> data = [(1, 'J'), (4, 'N'), (3, 'H'), (2, 'O')] >>> for item in data
工具.py import heapq class PriorityQueue: def __init__(self): self.heap=[] def push(se
我有相当多的 n=10000 个排序列表，每个列表的长度为 k=100。由于合并两个排序列表需要线性时间，我认为在深度为 log(n) 的树中递归合并长度为 O(nk) 的排序列表与 heapq.me
我是 python 的新手(使用 v3.x 语法)，希望得到有关 heapq 与排序的复杂性和性能的说明。 我已经为贪婪的“找到最佳工作安排”算法实现了基于 heapq 的解决方案。但后来我了解了将“
我的问题来自下面leetcode中的解决方案，我不明白为什么是O(k+(n-k)log(k))。 补充:可能复杂度不是这个，其实我不知道heappush()和heappop()的时间复杂度 # O(k
我正在尝试使用自定义排序谓词构建堆。由于进入它的值是“用户定义”类型，我无法修改它们的内置比较谓词。 有没有办法做类似的事情: h = heapq.heapify([...], key=my_lt_p
>>> from heapq import heappush >>> heap = [] >>> heappush(heap,(0,{"k":0})) >>> heappush(heap,(0,{"k
首先，我阅读了这个SO question但它实际上不包括我想要的方法。此外，否定实际值不适用于我的用例。 Heapq 文档:https://docs.python.org/3.6/library/he
我正在使用 heapq 对象来存储我实现的类的对象。 import heapq heap = [] element1 = Element('A', 1) element2 = Element('B',
我试图在我的程序中使用 Python 模块 heapq，但我在使用 heapq.heappop() 时遇到了一个奇怪的问题。该函数似乎没有返回堆中的最小元素。看看下面的代码: Python 2.7.1
我有一本包含 {key: count} 的字典，比如说status_count = {'管理分析':13859，'计算机程序员':72112}我正在尝试为 heapq.nlargest() 编写一个键
我最初尝试使用优先级队列编写算法来解决 15 题，但我的导师告诉我们，我们需要编写 a* 实现，并建议我们使用 heapq 而不是优先级队列。我无法找到我的 heapq 的长度/大小，也无法访问我的
我将一个名为 UNVISITED 的空列表转换为一个堆，这样: UNVISITED = [] heapq.heappush(UNVISITED, (a.f, a)) 我推送的对象a，是从一个类中实例化
如果堆化此 [(10,'Mike'),(20,'Jack'),(10,'Bob')] 并返回堆的最小值，它会保证返回 (10,'Mike') 而不是 (10,'Bob') 吗？ 最佳答案 no hea
每次 heapq.heapify 函数更改我的堆列表中的元素时，我都希望得到回调通知(顺便说一句，这是跟踪列表中的对象以及它们的索引如何获取所需要的改变了)。 我的计划是从 list 继承并重写 __
如何返回可迭代的第n大项的原始列表中的索引 heapq.nlargest(2, [100, 2, 400, 500, 400]) output = [(3,500), (2, 400)] 这已经花费了
我正在使用 Python 的 heapq 模块按升序和降序获取数据。 对于升序，我使用的是最小堆，它运行良好，如下所示: >>> from heapq import heapify, heappop
我希望拥有一堆对象，而不仅仅是数字。它们将具有堆可以排序的整数属性。在python中使用堆最简单的方法是heapq，但是在使用heapq时如何告诉它按特定属性排序呢？ 最佳答案 根据 document
我是一名优秀的程序员,十分优秀！