heap

堆是一种树形数据结构,其中子节点与父节点之间是一种有序关系。最大堆中父节点大于或等于两个子节点,最小堆父节点小于或等于两个子节点。Python的heapq模块实现了一个最小堆
import heapq
创建堆
  •     data = [1,5,3,2,8,5]
  •     heap = []
  •     for n in data:
  •         heapq.heappush(heap, n)
or
  •     heapq.heapify(data)
删除有最小值的元素
  •     print heapq.heappop(data) # print 1
查找其中包含的最大值与最小值(3表示要查找几个最值)
  •     print heapq.nlargest(3, data)
  •     print heapq.nsmallest(3, data)
  •     output:
  •     [8, 5, 5]
  •     [1, 2, 3]
对每个元素进行比较时, 会以price的值进行比较
  •     portfolio = [
  •     {'name': 'IBM', 'shares': 100, 'price': 91.1},
  •     {'name': 'AAPL', 'shares': 50, 'price': 543.22},
  •     {'name': 'FB', 'shares': 200, 'price': 21.09},
  • ]
  •     cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])  
添加元素
  •     heapq.heappush(heap, item) 把item添加到heap中(heap是一个列表)
先添加元素,后pop最小
  •     heapq.heappushpop(heap, item) 先把item加入到堆中,然后再pop,比heappush()再heappop()要快得多
先pop最小,后添加元素
  •     heapq.heapreplace(heap, item) 先pop,然后再把item加入到堆中,比heappop()再heappush()要快得多
合并多个列表
  •     heapq.merge(*iterables) 将多个列表合并,并进行堆调整,返回的是合并后的列表的迭代器
立即登录, 发表评论.
没有帐号? 立即注册