当前位置:   article > 正文

python heapq_Python 模块之heapq

heapq的特点

1、heapq介绍:

堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。( heapq库中的堆默认是最小堆)

最大堆,树种各个父节点的值总是大于或等于任何一个子节点的值。

最小堆,树种各个父节点的值总是小于或等于任何一个子节点的值。

我们一般使用二叉堆来实现优先级队列,它的内部调整算法复杂度为logN。

堆是一个二叉树,其中最小堆每个父节点的值都小于或等于其所有子节点的值。

整个最小堆的最小元素总是位于二叉树的根节点。

python的heapq模块提供了对堆的支持。 heapq堆数据结构最重要的特征是heap[0]永远是最小的元素

2、heapq方法介绍:

heappush(heap, item)

heapq.heappush(heap, item) 将item压入到堆数组heap中。如果不进行此步操作,后面的heappop()失效,

会直接返回原列表第一个值,而且必须从头开始heappush,不然也会返回原列表第一个值。

例:

a= [12,2,4,5,63,3,2]

heapq.heappush(a,123)>>>[12, 2, 4, 5, 63, 3, 2, 123]

b=heapq.heappop(a)>>>12

heappop(heap)

删除并返回最小值,因为堆的特征是heap[0]永远是最小的元素,所以一般都是删除第一个元素。

注意,如果不是压入堆中,而是通过append追加一个数值,堆的函数并不能操作这个增加的数值,或者说它堆对来讲是不存在的。

例:

a=[]

heapq.heappush(a,11)

heapq.heappush(a,2)

heapq.heappush(a,3)

heapq.heappush(a,4)

a.append(1)

b=heapq.heappop(a)>>b=2

heapq.heapify(list)

参数必须是list,此函数将list变成堆,实时操作。从而能够在任何情况下使用堆的函数

例:

a= [12,2,4,5,63,3,2]

heapq.heapify(a)

heapq.heappop(a)

heapq.heappushpop(heap, item)

是上述heappush和heappop的合体,同时完成两者的功能,注意:相当于先操作了heappush(heap,item),然后操作heappop(heap)

heapq.heapreplace(heap, item)

是上述heappop和heappush的联合操作。注意:与heappushpop(heap,item)的区别在于,顺序不同,这里是先进行删除,后压入堆

heapq.merge(*iterables)

将多个堆合并

a= [2, 4, 6]

b= [1, 3, 5]

c=heapq.merge(a, b)>>[1, 2, 3, 4, 5, 6]

heapq.nlargest(n, iterable,[ key])

查询堆中的最大n个元素

heapq.nsmallest(n, iterable,[ key])

查询堆中的最小n个元素

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/1020116
推荐阅读
相关标签
  

闽ICP备14008679号