【数据结构与算法python】完全二叉树的实现（优先队列和二叉堆）

1、引入

前面我们学习了一种FIFO数据结构队列，队列有一种变体称为“优先队列”。
如银行窗口取号排队， VIP客户可以插到队首，操作系统中执行关键任务的进程或用户特别指定进程在调度队列中靠前

• 优先队列的出队跟队列一样从队首出队；但在优先队列内部， 数据项的次序却是由“优先级”来确定：
• 高优先级的数据项排在队首，而低优先级的数据项则排在后面。
• 这样，优先队列的入队操作就比较复杂，需要将数据项根据其优先级尽量挤到队列前方。

2、定义

实现优先队列的经典方案是采用二叉堆数据结构
二叉堆能够将优先队列的入队和出队复杂度都保持在O(log n)
二叉堆的有趣之处在于， 其逻辑结构上像二叉树， 却是用非嵌套的列表来实现的！
最小key排在队首的称为**“最小堆min heap”，反之，最大key排在队首的是“最大堆max heap”**
为了使堆操作能保持在对数水平上， 就必须采用二叉树结构；
同样， 如果要使操作始终保持在对数数量级上， 就必须始终保持二叉树的“平衡”，树根左右子树拥有相同数量的节点

可采用“完全二叉树”的结构来近似实现“平衡”，完全二叉树，叶节点最多只出现在最底层和次底层，而且最底层的叶节点都连续集中在最左边，每个内部节点都有两个子节点， 最多可有1个节点例外，如下图的“18”节点

完全二叉树由于其特殊性， 可以用非嵌套列表， 以简单的方式实现， 具有很好性质，如果节点的下标为p，那么其左子节点下标为2p，右子节点为2p+1，其父节点下标为p//2

任何一个节点x， 其父节点p中的key均小于x中的key，这样，符合“堆”性质的二叉树，其中任何一条路径，均是一个已排序数列， 根节点的key最小 ，部分有序

3、功能分析

（1）二叉堆初始化

采用一个列表来保存堆数据，其中表首下标为0的项无用，但为了后面代码可以用到简单的整数乘除法，仍保留它。

（2）插入元素 insert(key)方法

首先，为了保持“完全二叉树”的性质，新key应该添加到列表末尾。

新key加在列表末尾，显然无法保持“堆”次序虽然对其它路径的次序没有影响，但对于其到根的路径可能破坏次序

需要将新key沿着路径来**“上浮”**到其正确位置，注意：新key的“上浮”不会影响其它路径节点的“堆”次序

（3）删除元素delMin()方法

移走整个堆中最小的key:根节点heapList[1]，为了保持“完全二叉树”的性质，只用最后一个节点来代替根节点

同样，这么简单的替换，还是破坏了“堆”次序解决方法：将新的根节点沿着一条路径“下沉”，直到比两个子节点都小
“下沉”路径的选择：如果比子节点大，那么选择较小的子节点交换下沉

（4）从无序表生成“堆”： buildHeap(lst)方法

我们最自然的想法是：用insert(key)方法，将无序表中的数据项逐个insert到堆中，但这么做的总代价是O(nlog n)，其实，用“下沉”法，能够将总代价控制在O(n)

4、代码实现

class BinHeap:
    # 二叉堆初始化
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    # 元素上浮
    def percUp(self,i):
        while i // 2 > 0:
          if self.heapList[i] < self.heapList[i // 2]:
             tmp = self.heapList[i // 2]
             self.heapList[i // 2] = self.heapList[i]
             self.heapList[i] = tmp
          i = i // 2
    # 插入元素
    def insert(self,k):
      self.heapList.append(k)
      self.currentSize = self.currentSize + 1
      self.percUp(self.currentSize)
    # 元素下沉
    def percDown(self,i):
      while (i * 2) <= self.currentSize:
          mc = self.minChild(i)
          if self.heapList[i] > self.heapList[mc]:
              tmp = self.heapList[i]
              self.heapList[i] = self.heapList[mc]
              self.heapList[mc] = tmp
          i = mc
    # 寻找小值索引
    def minChild(self,i):
      # 需要比较的节点是否为最后一个节点，如果是的话，只能是左子节点
      if i * 2 + 1 > self.currentSize:
          return i * 2
      else:
          if self.heapList[i*2] < self.heapList[i*2+1]:
              return i * 2
          else:
              return i * 2 + 1
    # 删除最小值  
    def delMin(self):
      retval = self.heapList[1]
      self.heapList[1] = self.heapList[self.currentSize]
      self.currentSize = self.currentSize - 1
      self.heapList.pop()
      self.percDown(1)
      return retval
    # 通过无序表创建二叉堆
    def buildHeap(self,alist):
      # 从最后节点的父节点开始，因为叶节点无需下沉
      i = len(alist) // 2
      self.currentSize = len(alist)
      self.heapList = [0] + alist[:]
      while (i > 0):
          self.percDown(i)
          i = i - 1

5、测试代码及结果

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())