- Python算法详解
- 张玲玲
- 573字
- 2020-06-27 17:50:53
4.5.1 Python中的堆操作
在Python中对堆这种数据结构进行了模块化处理，开发者可以通过调用heapq模块来建立堆这种数据结构，同时heapq模块也提供了相应的方法来对堆进行操作。在heapq模块中包含如下成员。
· heapq.heappush(heap, item)：把一个item项压入堆heap，同时维持堆的排序要求。
· heapq.heappop(heap)：弹出并返回堆heap里值最小的项，调整堆排序。如果堆为空，抛出IndexError异常。
· heapq.heappushpop(heap, item)：向堆heap里插入一个item项，并返回值最小的项。它组合了前面两个函数，这样更有效率。
· heapq.heapify(x)：在线性时间内，将列表x放入堆中。
· heapq.heapreplace(heap, item)：弹出值最小的项，并返回相应的值，最后把新项压入堆heap。如果堆为空，抛出IndexError异常。
· heapq.merge(*iterables)：合并多个堆排序后的列表，返回一个迭代器来访问所有值。
· heapq.nlargest(n, iterable, key=None)：从数据集iterable中获取n项的最大值，以列表方式返回。如果提供了参数key，则key是一个比较函数，用来比较元素之间的值。
· heapq.nsmallest(n, iterable, key=None)：从数据集iterable中获取n项的最小值，以列表方式返回。如果提供了参数key，则key是一个比较函数，用来比较元素之间的值。相当于sorted(iterable, key=key)[:n]。
下面的实例文件dui1.py演示了使用上述函数实现堆队列的过程。
源码路径：daima\第4章\dui1.py
import heapq
h = []
#使用heappush()把一项压入堆heap，同时维持堆的排序要求。
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
heapq.heappush(h, 4)
print(heapq.heappop(h))
heapq.heappush(h, 5)
#使用heapq.heappop(heap)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
heapq.heappush(h, 4)
print(heapq.heappop(h))
print(heapq.heappop(h))
#使用heapq.heappushpop(heap, item)
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
print(heapq.heappushpop(h, 4))
#使用heapq.heapify(x)
h = [9, 8, 7, 6, 2, 4, 5]
heapq.heapify(h)
print(h)
#使用heapq.heapreplace(heap, item)
heapq.heapify(h)
print(heapq.heapreplace(h, 1))
print(h)
#使用heapq.merge(*iterables)
heapq.heapify(h)
l = [19, 11, 3, 15, 16]
heapq.heapify(l)
for i in heapq.merge(h,l):
print(i, end = ',')
执行后会输出：
2 2 4 2 [2, 6, 4, 9, 8, 7, 5] 2 [1, 6, 4, 9, 8, 7, 5] 1,3,6,4,9,8,7,5,11,19,15,16,