1. 模块:heapq
1.1 模块方法汇总
__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
'nlargest', 'nsmallest', 'heappushpop']
"""
heappush: Push item onto heap, maintaining the heap invariant.
heappop: Pop the smallest item off the heap, maintaining the heap invariant.
heapify: ransform list into a heap, in-place, in O(len(x)) time.
heapreplace: Pop and return the current smallest value, and add the new item.
merge: Merge multiple sorted inputs into a single sorted output.
nlargest: Find the n smallest elements in a dataset. Equivalent to: sorted(iterable, key=key)[:n]
nsmallest: Find the n largest elements in a dataset. Equivalent to: sorted(iterable, key=key, reverse=True)[:n].
heappushpop: Fast version of a heappush followed by a heappop.
"""
1.2 方法详解和实践
refer: Python标准库模块之heapq refer: 创建堆
1.2.1 创建堆 heapify
-
概念: 创建堆 指的是初始化一个堆实例。在创建 堆 的过程中,我们也可以同时进行 堆化 操作。堆化 就是将一组数据变成 堆 的过程。 -
创建方法:
- 使用一个空列表,然后使用heapq.heappush()函数把值加入堆中;
- 或者使用heap.heapify(list)转换列表成为堆结构
时间复杂度: O(N) 空间复杂度: O(N) -
语法:heapify(list) import heapq
seqs = [5, 2, 4, 7, 11, 3, 12, 65, 34]
heap = []
for v in seqs:
heapq.heappush(heap, v)
print(heap)
heapq.heapify(seqs)
print(seqs)
print([heapq.heappop(seqs) for _ in range(len(seqs))])
import heapq
minHeap = []
heapq.heapify(minHeap)
heapWithValues = [3,1,2]
heapq.heapify(heapWithValues)
maxHeap = [1,2,3]
maxHeap = [-x for x in maxHeap]
heapq.heapify(maxHeap)
1.2.2 插入元素 heappush
1.2.3 获取元素
堆获取元素通常指获取堆顶元素
-
语法:heap[0]
minHeap[0]
maxHeap[0]*-1
1.2.4 删除堆顶元素 heapq.heappop
1.2.5 替换堆顶元素 heapq.heaprepalce
-
语法: heapq.heapify(heap, item) import heapq
seqs = [5, 2, 4, 7, 11, 3, 12, 65, 34]
heapq.heapify(seqs)
print(seqs)
heapq.heapreplace(seqs, 200)
print(seqs)
|