第5讲 | 数据结构与算法 | 【堆】

转载需联系VX【econe0219】

堆（Heap）

堆实际就是树的一种，关于树这种数据结构后续文章会详细讲。不过堆也很好理解，所以直接拿出来说下，而且下篇文章要用到堆这个数据结构。

堆这种特殊的树满足两个条件：

• 堆是一个完全二叉树；
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树每个节点的值。

完全二叉树就是除了最后一层，所有层都是满节点，而且最后一层的节点都是左排列（要么左右子节点都有，要么只有左子节点）。堆的节点大于等于其左右子节点的堆称为“大顶堆”，小于等于其左右子节点的堆称为“小顶堆”，分别如下图所示：

堆的存储

如果用数组来堆的话，存储大顶堆的数组如下：（关于树的存储细节后面文章讲）

为了容易计算字节点位置，从数组的第二个位置开始存储，那么数组中第 $i$ 个下标的左子节点在堆中的下标位置是 $2i$，数组中第 $i$ 个下标的右子节点在堆中的下标位置是 $2i+1$，数组中第 $i$ 个下标的父节点在堆中的下标位置是 $i/2$。

如果为了不浪费存储空间就从第一个位置开始存储，那么左右子树和父节点的下标分别为 $2i+1,\ 2i+2, \ (i-1)/2$。注意此时堆顶元素下标是从0开始算。

即：

parent = int((i-1)/2)
left = 2 * i + 1
right = 2 * i + 2
复制代码

堆的插入操作

如果直接插入一个数放到堆的末尾，会发现就不满足堆的必要条件了，即不是一个堆了，所以此时还有进行“堆化（Heapify）”来形成一个新的堆。

堆化可以从上往下，也可以从下往上。也就是说顺着节点所在路径，向上或者向下对比，交换。如下图所示是一个自下而上的堆化过程，新插入的节点与父节点对比，若新节点大于父节点，则交换，依次向上重复这个过程，直到满足堆的必要条件。堆化结束也就完成了插入的过程。

堆的删除操作

假设要删除大顶堆的最大元素，也就是堆顶元素。首先把堆顶元素和堆的最后一个元素交换，并删除最后一个元素，（该做法的原因是为了满足构成堆的第一个必要条件），或者直接把堆顶元素删掉，把最右下节点元素放到堆顶也可以。然后从上往下，依次实现堆化过程，堆化结束也就完成了删除操作。动态演示图图下所示：

还有一个小问题，就是堆顶元素到底是和左子节点交换呢还是该和右子节点交换呢，原理上并不限制。不管是和哪个节点交换都是满足堆的条件的，不过我觉得这里应该选择左右子节点中最大的那个，这样可以处理的堆更平衡。

代码实现

大顶堆

class Array(object):
    """用 python list 实现一个 array"""
    
    def __init__(self, size=32):
        self._size = size
        self._items = [None] * size
    
    def _getitem__(self, index):
        """通过索引取值"""
        return self._items[index]
    
    def __setitem__(self, index, vaule):
        """给list赋值"""
        sele._item[index] = value
        
    def __len__(self):
        """返回array长度"""
        return self._size
    
    def __iter__(self):
        """返回数组中的值"""
        for item in self.items:
            yield item

class MaxHeap(object):     
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self._elements = Array(maxsize)
        self._count = 0
    
    def __len__(self):
        return self._count
    
    def insert(self, item):
        """插入数据"""
        if self._count >= self.maxsize:
            raise Exception('full')     # 引发一个异常
        self._elements[self._count] = item   # 堆尾插入数据
        self._count += 1
        self._siftup(self._count-1)     # 自下而上堆化，以满足堆的充要条件
        
    def _siftup(self, ndx):     # ndx：list中数据的位置
        """自下而上的堆化实现"""
        if ndx > 0:
            parent = int((ndx-1)/2)     # 数据在堆中对应的下标位置
            if self._elements[ndx] > self._elements[parent]:     # 子节点大于父节点交换位置
                self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]
                self._siftup(parent)     # 向上递归实现
            
    def pop(self):
        """删除堆顶元素"""
        if self._count <= 0:
            raise Exception('empty')
        value = self._elements[0]     
        self._count -= 1     # 缩小list长度，相当于把最后一个数删掉
        self._elements[0] = self._elements[self._count]     # 最右下的节点数据放在堆顶
        self._siftdown(0)     # 从堆顶开始，自上而下开始堆化
        return value

    def _siftdown(self, ndx):
        """自上而下的堆化实现"""
        left = 2 * ndx + 1
        right = 2 * ndx + 2
        # 选择左右子节点中最大的那个
        largest = ndx
        if (left < self._count and     # 存在左子树
            self._elements[left] >= self._elements[largest] and
            self._elements[left] >= self._elements[right]):     # 如果不要求左子树大于右子树也是可以的，但是这样的堆更平衡
            largest = left
        elif right < self._count and self._elements(right) >= self._elements(largest):
            largest = right
        if largest != ndx:
            self._elements[largest], self._elements[ndx] = self._elements[ndx], self._elements[largest]
            self._siftdown(largest)     # 调用自身递归        
复制代码

小顶堆和大顶堆的实现只有堆化那部分有点小小区别（满足堆的必要条件即可），这里就不再写了。

（代码实现参考链接）

**插入和删除时间复杂度分析：**根据堆的插入和删除过程来看，主要的操作其实都是堆化，无非就是自上而下还是自下而上。堆化的时间复杂度和树的高度是成正比的，因为堆化的路径基本是确定的，不会出现同一层上节点的交换。而且完全二叉树的高度不超过 $\log_2n$ （原因在后续讲树的时候细说），所以，删除和插入的时间复杂度都是 $O(\log n)$。

建堆

建立一个堆有两种方式[6]：

1）第一种就是如上所述插入的方式，假设最开始只有一个节点，从根节点开始一个数一个数的插入，最终建立一个完整的堆。这种情况，如果每次插入都不需要堆化（例如在最大堆，插入数据总是小于父节点），那么最优时间复杂度就是 $O(n)$。最坏情况是插入数据每次都要调整到根节点，堆化的时间复杂度是 $O(\log n)$，n个数据都要堆化一次，所以这种情况下的时间复杂度就是 $O(n\log n)$。第一种情况应用的场景是，事先不知道有多少数据，需要通过不断插入来构建。

2）更常见的情况是，已经有一棵树或一个数组，要把这棵树转换成堆。这时建堆的过程就和第一种方式完全相反了。画了如下示意图，结合图可以很好的理解。数据处理过程是从后往前，因为最后面的叶子节点不需要堆化（$n/2+1\sim n$的节点都是叶子节点），所以直接从最后那个叶子节点的父节点开始堆化，堆化过程是从上往下，结合图来分析就明白了。

第一次对13堆化，第二次对10堆化，第三次对12堆化，第四次对5堆化，最后就得到如图5的二叉堆。

” loading=”lazy” class=”medium-zoom-image”>

再看下这种建堆方式的时间复杂度，每次堆化是 $O(\log n)$，那n次堆化最后结果就是$O(n\log n)$吗？？？其实不是的，上面这个有9个数据，建堆过程中只对4个数据进行堆化，远远用不到全部的n=9个，而且都不需要调整到根节点，所以这种方式就不能用如上分析方法了。

需要实现堆化的节点的时间复杂度和该节点的高度是成正比的，所以实际上我们只需要把每个节点的高度加起来，也就相当于解得总的时间复杂度。

” loading=”lazy” class=”medium-zoom-image”>

总的高度 $H=2^0*h+2^1*(h-1)+2^2*(h-2)+\cdots+2^{h-1}*1$，求出这个高度即可。用错位相减法就可以解出来，先令 $H’=2H$，那么 $H=H’-H=-h+2^1+2^2+2^3+\cdots++2^h=2^{h+1}-h-2$，又 $h=\log_2n$，所以最后可知时间复杂度是$O(n)$。

《数据结构与算法》专栏完整版在公号【书伟认视界】中查看，转载需联系VX【econe0219】

.