Python——heap

发布时间：2019-09-10 08:50:04编辑：auto阅读（1714）

    通过优先队列可以构造堆，堆是一种实用的数据结构。尽管Python中没有独立的堆类型，但是包含了一些对操作函数的模块，这个模块叫heapq，主要的操作包含如下几个：

    heappush(heap,x):x元素插入堆
    heappop(heap):弹出对中最小元素
    heapify(heap):将heap属性强制应用到任意一个列表
    hrapreplace(heap,x):将heap中最小元素弹出，同时x元素入堆
    hlargest(n,iter):返回iter中第n大的元素
    hsmallest(n,iter):返回iter中第n小的元素

    堆的定义和使用如下：

    >>> from heapq import *
>>> from random import shuffle
>>> x=[1,2,3,4,5,6]
>>> shuffle(x)
>>> heap=[]
>>> for i in x:
    heappush(heap,i)
>>> heap
[1, 3, 2, 6, 4, 5]
>>>

    注：shuffle函数将列表顺序打乱
    堆元素的追加：

    >>> heap
[1, 3, 2, 6, 4, 5]
>>> heappush(heap,0)
>>> heap
[0, 3, 1, 6, 4, 5, 2]
>>>

    删除堆中元素：

    >>> heap
[0, 3, 1, 6, 4, 5, 2]
>>> heappop(heap)
0
>>> heap
[1, 3, 2, 6, 4, 5]
>>> heappop(heap)
1
>>> heap
[2, 3, 5, 6, 4]
>>>

    heapify函数将列表生成堆：

    >>> x=[1,4,2,3,5,4]
>>> heapify(x)
>>> x
[1, 3, 2, 4, 5, 4]
>>> heappop(x)
1
>>> heappop(x)
2
>>> x
[3, 4, 4, 5]
>>>

    hrapreplace函数弹出最小元素将另一个元素加入堆：

    >>> x
[3, 4, 4, 5]
>>> heapreplace(x,0)
3
>>> x
[0, 4, 4, 5]
>>>

关键字：

上一篇： Python中的StringIO与cSt

下一篇： 安卓完美使用python