树4，二叉树的特例——堆

作者: 小碧小琳 | 来源:发表于2018-07-29 14:57 被阅读0次

堆分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。

大致讲一下有用的几点，二叉堆实现只需要用构造函数，得到一个元素为零的list，size为0的一个类就行。然后通过perUp方法不断地插入数据项，最终便可得到最大最小值，而且，操作复杂度也仅是O(logn)。

一、利用“优先队列”实现快速查找最大值或最小值

1.1认识“优先队列”

前面我们学习了“先进先出”的数据机构：队列。
队列有一个重要的变种叫做“优先队列”。
队列内部的数据按照一定的优先级排列。有最高优先级的数据项排在队首，优先级最低的数据项排在队尾。

从这里我们可以发现，如果实现了优先队列，那么快速找到这批数据中的最大值或最小值是很方便的——只需要执行出队操作就行。

注意：需要指出的是，下面的二叉堆列表中的数据，并不是按照从大到小或者从小到大的顺序排列的。只是保证了队首的是最大值或最小值。此时的操作复杂点依然是O(logn)。

1.2如何实现优先队列

前面我们实现队列是基于列表的结构实现的，如果我们还是用排序函数结合原始的队列来实现优先队列，这里的时间复杂度就很高了：在列表中插入一个数据项的复杂度是O(n)，列表排序的复杂度是O(nlogn)。采取这种方法去实现优先队列，跟不实现优先队列去查找最大最小值是没有区别的。

那么有没有别的方法来降低实现优先队列的复杂度呢？
答：通过二叉堆数据结构实现优先队列。

二叉堆能将优先队列的入队和出队复杂度都保持在O(logn)。
尽管二叉堆的逻辑结构用图形表示很像二叉树，但是我们可以只用一个列表来实现它。
最大成员key排在对手的称为最小堆，反之称之为最大堆。

二、二叉堆的实现

需要考虑二叉堆应该具有怎样一种结构，二叉堆里的数据应该有怎样的次序性，弄清了这两个，再去添加方法，就更容易理解多了。

2.1 二叉堆操作

如同学习前面几个数据结构的步骤一样，我们确定了二叉堆的基本性质，还需要确定二叉堆应该具有哪些基本操作。
对应到代码上，就是我们先构造一个二叉堆类，再不断地去给这个类添加方法。而这些方法都是二叉堆应该具有的基本操作。

数据结构二叉堆的基本操作定义如下：

BinaryHeap():创建一个新的空二叉堆对象
insert(k):加入一个新数据项到堆中
findMin():返回堆中的最小项,最小项仍保留在堆中
delMin():返回堆中的最小项,同时从堆中删除
isEmpty():返回堆是否为空
size():返回堆中数据项的个数
buildHeap(list):从一个 key 列表创建新堆

2.2 二叉堆的结构性质

2.2.1、结构：二叉堆应该具有完全树的结构

背景：

1、二叉树的操作为对数级
这与上面我们想要用二叉堆降低操作复杂度相吻合。所以用二叉树来实现二叉堆。
2、用完全二叉树将堆操作始终保持在对数水平上。
要想将二叉树的操作保持在对数水平上，我们就需要始终保持二叉树的“平衡”（即左右子树有着相同数量的节点）。因此，我们需要用“完全二叉树”结构来近似的实现“平衡”。
完全二叉树，每个内部节点都有两个子节点，最多只有一个节点例外。
3、完全二叉树可以用列表来实现。
完全树不需要使用节点，引用来实现，因为对于完全树，如果节点在列表中的位置为p，那么其左子节点的位置为2p，类似的，其右子节点的位置为2p+1。
所以对于找任意节点的父节点时，可以直接利用Python的整数除法。若节点在列表中的位置为n，那么父节点的位置是n//2。

下面是完全树的例子以及树的列表表示。

从中可以看出，33和17的父节点，通过n/2即可求得，为14。

至此我们可以理出一条思路：想要实现优先队列，就要用二叉堆。想要实现二叉堆，就要用完全树。

为什么使用完全树？

因为完全树可以用列表实现（这与队列结构相符），寻找父子节点只需要整除index即可。
因为完全树的操作复杂度始终为对数级（这与用二叉堆来简化复杂度相符）。

2.2.2、性质：二叉堆的次序性

已经解释了二叉堆应该具有什么样的结构（操作复杂度的问题解决了）。那么二叉堆中的数据应该具有什么样的性质呢？

在堆里存储数据项的方法依赖于维持堆次序。。所谓堆次序，是指堆中任意一个节点x，其父节点p中的key均小于或等于x中的key。

做个比喻，如果只有完全树的结构，那么优先队列只是拥有了血肉。只能进行复杂度比较低的操作。如果再加上堆次序，那么优先队列就拥有了灵魂，可以在进行复杂度比较低的操作同时，将内在的数据项按照优先级排列。

如上图中的完全树，就是一个具有堆次序的完全树。

三、二叉堆操作的实现

在二叉堆得到结构与性质的基础上，去讨论用代码去实现二叉堆一些具体操作，就比较容易了。

3.1 用构造函数来实现二叉堆

因为可以采用一个列表来保存堆数据，构造函数仅仅需要初始化一个列表和一个currentSize来跟踪记录堆当前的大小。列表首位下标为0，是为了后面代码可以用到简单的整数乘除法，仍保留它。

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

3.2 insert(key)方法

若是直接将数据添加到列表末尾，无法保持堆的次序性。
不过，我们可以通过比较新加入的数据项和父节点的方法来恢复堆的次序性。如果新加入的数据项比父节点要小，可以把它与父节点互换位置。
如下图所示

当我们让一个数据项“上浮”时，我们保证了新节点与父节点以及其他兄弟节点之间的堆次序。当然，如果新节点非常小，我们可能仍需要把它向上交换到另一个层级。事实上，我们需要不断交换，直到到达树的顶端。

下面代码所示是“上浮”方法，它把一个新节点“上浮”到其正确位置来保持堆次序。这里很好地体现了我们在heapList中没有用到的元素0的重要性。只需要做简单的整数除法:将当前节点的下标除以2，我们就能计算出任何节点的父节点。

3.2.1、将新节点从队尾放到正确位置上的上浮函数perUp()

1、传入的i参数是整个列表的长度。此时的新节点就在i位置。
2、i//2，得到新节点的父节点位置，并比较父节点与新节点的大小
3、若父节点比新节点要小，边利用tmp变量，交换二者数据项
4、新节点上浮以后，再比较此时的新节点的父节点与新节点的大小，若是有必要，继续执行上浮操作。

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

3.2.2、插入新节点的方法insert(key)

一开始构造函数构造的二叉堆具有两个属性，一个是列表，一个是当前的size。因此，插入一个新节点，就需要向列表中插入一个节点，并且修改当前的size。

1、在列表中添加节点
2、当前size加1
3、将新节点放到正确的位置中去（perUp函数）

def insert(self,k):
    self.heapList.append(k)
    self.currentSize = self.currentSize + 1
    self.percUp(self.currentSize)

3.3 、delMin()，删除最小项

找到并删除二叉堆中的最小项，是很容易的。但是困难的是，移走根节点的数据项后如何恢复堆结构和堆次序。（即保持二叉堆的结构和性质不变。）
分两步：

1、保持结构不变：用最后一个节点来代替根节点。
因为移走最后一个节点，堆的结构也不会变化。
2、保持堆次序不变
合理的“下沉”根节点，来回复堆次序。

3.3.1、perDown（），下沉方法

按照上述所说，先说对于一个根节点，怎样下沉。
下沉用到了两个辅助函数：perDown，minChild。

1、perDown
父节点比最小的子节点要大，那么就违反了堆次序，就要下沉。通过设置tmp变量，交换根节点与子节点的数据项。
2、minChild
这个函数，每次返回父节点下的最小子节点的index。
至于为什么是最小子节点，设想一下，假设不是最小子节点，而是随机选取一个子节点与父节点替换，那么很可能在最上面的根节点的数据项不是最小值。
所以在每次下沉的时候，都需要判断一下父节点下的最小子节点的index。

def percDown(self,i):
    #循环结束条件：当前节点的子节点超过size，说明当前节点已经到达完全树底层，不用再循环了
    #比如树中的第六（19），第七个数据项（21）
    while (i * 2) <= self.currentSize:
        #调用minChild，得到当前节点的最小子节点的index
        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
        #下沉以后，得到当前节点的index
        i = mc

def minChild(self,i):
    #这个判断，是说假设当前节点只有一个子节点时的情况，就不用比较最小子节点了
    #直接返回唯一的子节点即可，比当第四个数据项只有一个子节点33时，应该执行这个操作
    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

至此，通过perDown，我们不但可以维持堆结构不变，还能保证堆次序不变。

3.3.2、delMin():返回堆中的最小项,同时从堆中删除

删除一个节点，同样需要对list进行两个属性的改变，一个改变size，一个是删掉一个节点。

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

3.4、从无序表中生成一个二叉堆

有关二叉堆的最后一部分便是找到方法从无序表生成一个“堆”。我们最自然的想法是：用insert（key）方法，将无序表中的数据项逐个插入到堆中。对于一个排好序的列表，我们可以用二分搜索找到合适的位置来插入下一个key，操作复杂度是O(logn).然而插入一个数据项到列表中间需要将列表其他数据项移动为新节点腾出位置，操作复杂度是O(n).因此用insert（key）方法的总代价是O(nlogn)。其实，我们能直接将整个列表生成堆，将总代价控制在O（n）。下面所示是生成堆的操作代码。

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

注意在while中，从列表中间开始，每次i-1，回溯到根节点，使用perDown方法，保证了最大子节点总是下沉。这种下沉操作一直持续到根节点，若根节点不是最小值，也会一直下沉，知道完成二叉堆。原理就不在此证明了。但是执行操作的话，比如在i等于1为根节点时，9会一直下降到底。