Python-heapq堆

1.堆介绍

• 堆是非线性的树形的数据结构，有两种堆,最大堆与最小堆。（ heapq库中的堆默认是最小堆）。
  最大堆，树种各个父节点的值总是大于或等于任何一个子节点的值。
  最小堆，树种各个父节点的值总是小于或等于任何一个子节点的值。
  
• 我们一般使用二叉堆来实现优先级队列,它的内部调整算法复杂度为logN。堆是一个二叉树，其中最小堆每个父节点的值都小于或等于其所有子节点的值。整个最小堆的最小元素总是位于二叉树的根节点。
• python的heapq模块提供了对堆的支持。 heapq堆数据结构最重要的特征是heap[0]永远是最小的元素。

2.堆的基本技巧

• 常用方法：nlargest(),nsmallest(),heapify(),heappop()；
• 如果需要的个数较小，使用nlargest或者nsmallest比较好；
• 如果需要的个数已经接近了序列长度，使用sorted()[:N]获取前N个数据比较好；
• 如果只需要唯一一个最大或最小值，则直接使用max()或者min()。

3.heapq堆的常用方法

• heapq.heappush(heap, item)
  heap为定义堆，item增加的元素。
• heapq.heapify(list)
  将列表转换为堆。
• heapq.heappop(heap)
  删除并返回最小值，因为堆的特征是heap[0]永远是最小的元素，所以一般都是删除第一个元素。
• heapq.heapreplace(heap.item)
  删除并返回最小元素值，添加新的元素值。
• heapq.heappushpop(list, item)
  判断添加元素值与堆的第一个元素值对比；如果大，则删除并返回第一个元素，然后添加新元素值item.如果小，则返回item. 原堆不变。
• heapq.merge(a1, a2, …)
  将多个堆合并。
• heapq.nlargest(n, heap_name)
  查询堆中最大的n个元素。
• heapq.nsmallest(n, heap_name)
  查询堆中最小的n个元素。
• 使用heapq编写优先级队列

  class PriorityQueue:
      def __init__(self):
          self.__queue = []
          self.__index = 0
          
      def push(self, item, priority):
          heapq.heappush(self.__queue, (-priority, self.__index, item))
          # 第一个参数：添加进的目标序列
          # 第二个参数：将一个元组作为整体添加进序列，目的是为了方便比较
          # 在priority相等的情况下，比较_index
          # priority为负数使得添加时按照优先级从大到小排序，因为堆排序的序列的第一个元素永远是最小的
          self.__index += 1
          
      def pop(self):
          # 返回按照-priority 和 _index 排序后的第一个元素(是一个元组)的最后一个元素(item)
          return heapq.heappop(self.__queue)[-1]