• ## heapq

2020-01-09 12:33:43
heapq是python自带的堆+优先级队列 官网https://docs.python.org/3.7/library/heapq.html 要点1：heapq实现的是小顶堆 要点2：大顶堆的做法是： [-i for i in heap] 下面是它的类函数 heapq.heappush(heap,item...

heapq是python自带的堆+优先级队列
官网https://docs.python.org/3.7/library/heapq.html
要点1：heapq实现的是小顶堆
要点2：大顶堆的做法是： [-i for i in heap]
下面是它的类函数
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].
heapq.heappushpop(heap,item) 前面两个操作合体
Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().
heapq.heapify(x) 堆化（列表或者map）
Transform list x into a heap, in-place, in linear time.
heapq.heapreplace(heap,item) //注意比较和pushpop的区别。元素值在任意时刻固定
Pop and return the smallest item from the heap, and also push the new item. The heap size doesn’t change. If the heap is empty, IndexError is raised.
This one step operation is more efficient than a heappop() followed by heappush() and can be more appropriate when using a fixed-size heap. The pop/push combination always returns an element from the heap and replaces it with item.
The value returned may be larger than the item added. If that isn’t desired, consider using heappushpop()instead. Its push/pop combination returns the smaller of the two values, leaving the larger value on the heap.
The module also offers three general purpose functions based on heaps.
heapq.merge(*iterables,key=None,reverse=False)
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).
Has two optional arguments which must be specified as keyword arguments.
key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).
reverse is a boolean value. If set to True, then the input elements are merged as if each comparison were reversed. To achieve behavior similar to sorted(itertools.chain(*iterables), reverse=True), all iterables must be sorted from largest to smallest.
Changed in version 3.5: Added the optional key and reverse parameters.
heapq.nlargest(n,iterable,key=None) topk最大
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 iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key, reverse=True)[:n].
heapq.nsmallest(n,iterable,key=None) topk最小
Return a list with the n smallest 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 iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key)[:n].
The latter two functions perform best for smaller values of n. For larger values, it is more efficient to use the sorted() function. Also, when n==1, it is more efficient to use the built-in min() and max() functions. If repeated usage of these functions is required, consider turning the iterable into an actual heap.


展开全文
• python heapqpython heapq python heapq 堆是一个二叉树，它的每个父节点的值都会小于或等于所有孩子节点的值。它使用了数组来实现：从零开始计数，对于所有的k，都有heap[k] <= heap[2k+1]和heap[k] <= heap...
python heapqpython heapq
python heapq
堆是一个二叉树，它的每个父节点的值都会小于或等于所有孩子节点的值。它使用了数组来实现：从零开始计数，对于所有的k，都有heap[k] <= heap[2k+1]和heap[k] <= heap[2*k+2] 。为了便于比较，不存在的元素被认为是无限大。堆最有趣的特性在于最小元素总是在根节点。
初始话一个堆，可以使用list来初始话，或者可以通过一个函数heapify()来把list转化成堆。

heapq.heappush(heap, item)
将item的值加入到堆中，保持堆的不变性

heapq.heappop(heap)
弹出并返回heap的最小元素，保持堆的不变性。如果堆为空，抛出IndexError。使用heap[0]可以访问最小的元素而不弹出它。

heapq.heappushpop(heap, item)
将item放入堆中，然后弹出并返回heap的最小元素。该操作类似于先heapq.heappush(heap, item)和heapq.heappop(heap)的组合

heapq.heapify(x)
将list x抓换成堆。

heapreplace(heap, item)
弹出并返回heap中最小的一项，同时推入新的item。如果堆为空报错IndexError
类似于heapq.heappop()和heapq.heappush（）的组合。

heapq.merge(*iterable, key=None, reverse=False)
将多个已排序的输入合并为一个已排序的输出。返回已排序的值的iterator。

heapq.nlargest(n, iterable, key=None)
从iterable所定义的数据集中返回前n个最大元素组成的列表。

heapq.nsmallest(n, iterable, key=None)
从iterable所定义的数据集中返回前n个最小元素组成的列表。


展开全文
• heapq有两种方式创建堆， 一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中，另外一种就是使用heap.heapify(list)转换列表成为堆结构 import heapq # 第一种 """ 函数定义： heapq.he...
该模块提供了堆排序算法的实现。堆是二叉树，最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。
创建堆
heapq有两种方式创建堆， 一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中，另外一种就是使用heap.heapify(list)转换列表成为堆结构
import heapq

# 第一种
"""
函数定义：
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))，但返回的是可迭代的。
"""
函数定义：
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))

访问堆内容
堆创建好后，可以通过heapq.heappop() 函数弹出堆中最小值。
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() 函数
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() 函数
"""
函数定义：
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]
"""

这两个函数还接受一个key参数，用于dict或其他数据结构类型使用
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应用
实现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) 类似，但是它是不稳定的。
堆的值可以是元组类型，可以实现对带权值的元素进行排序。
>>> 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')

转载于:https://www.cnblogs.com/xiao-xue-di/p/10552264.html
展开全文
• heapq 模块 标签（空格分隔）： pythoncook笔记 1. 查找最大或最小的N个元素（nlargest ,nsmallest） import heapq nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] print(heapq.nlargest(3, nums)) # ...
heapq 模块

标签（空格分隔）： pythoncook笔记

1. 查找最大或最小的N个元素（nlargest ,nsmallest）

import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]

两个函数都能接受一个关键字参数，用于更复杂的数据结构中：

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'])

2. 优先队列的实现

import heapq

class PriorityQueue:
def __init__(self):
self._queue = []   # 初始化一个列表来储存队列
self._index = 0    # 初始化信号

def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))  # 向队列里添加元素，并添加优先级
self._index += 1    # 使每个添加进队列的元素具有不同的信号予以区分

def pop(self):
# heapq.heappop会删除队列中最小的元素并返回，这正好照应了之前把优先级设为负数的构想
return heapq.heappop(self._queue)[-1] 

index的作用是在两个元素具有相同的优先级的情况下，可以按照它们的插入顺序来将元素跳出队列
看一下代码你就知道为什么了

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

当加上index变量组成三元组进行比较时，由于每个元素的index不一样，所以就能很好的避免上面的问题了

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>`
展开全文
• Python heapq模块 heapq模块提供了如下几个函数： 函数 用法 heapq.heappush(heap, item) 把item添加到heap中（heap是一个列表） heapq.heappop(heap) 把堆顶元素弹出，返回的就是堆顶 heapq....
• Python中的heapq模块提供了一种堆队列heapq类型,这样实现堆排序等算法便相当方便,这里我们就来详解Python中heapq模块的用法,需要的朋友可以参考下
• import heapq if __name__ == '__main__': # heapq.heappush 参数1用于排序的空列表，参数二需要被排序的列表，键入对排列中，被排序 # heapq.heappop(heap)弹出堆排序列表中一个元素 nums = [2, 3, 5, 1, 54, ...
• Python数据结构常用模块：collections、heapq、operator、itertoolsheapq堆是一种特殊的树形结构，通常我们所说的堆的数据结构指的是完全二叉树，并且根节点的值小于等于该节点所有子节点的值常用方法heappush(heap,...
• 主要介绍了Python heapq使用详解及实例代码的相关资料,需要的朋友可以参考下
• 使用堆可以非常方便的...import heapq nums = [1, 8, 2, 23, 7, -5, 18, 23, 42, 37, 2] heapq.heapify(nums) print(nums) print(heapq.heappop(nums)) print(nums) print(heapq.heappop(nums)) print(nums) print(...
• 主要给大家介绍了关于Python中heapq模块的相关资料，文中通过示例代码介绍的非常详细，对大家学习或者使用python具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧

...