堆的实现与应用

计算机科学有一些容易让人混淆的概念或名词，具体表现为不同的概念使用了相同的名词，或者相同的概念使用了不同的名词。导致这样的问题可能出于翻译或历史等原因，需要根据上下文环境来澄清。堆（heap）是众多让人混淆的概念中的一个。堆可能表示一种数据结构，也可以是内存空间中的堆。两者并非毫无联系，早期 Lisp 使用堆这种数据结构来进行内存分配。本文讲的是数据结构的堆。

堆是一种树状的数据结构，满足以下特性：

任意节点的值不小于（或不大于）子节点的值
是一个完全二叉树，除了最底层外，其他层的节点全部被填入，且最底层从左到右填入。

堆分为最大堆和最小堆，本文只讨论最大堆。根据对称性，最小堆代码很容易修改得到。

堆的实现

堆可以直接通过树来实现。由于堆是一个完全二叉树，节点间的关系十分简单，也可以通过数组来实现。下面是一个简单的示例：

树：
       10
     /    \ 
    8      6
   / \    / \
  4   5  7   2
 / \
3   1

数组：
[10, 8, 6, 4, 5, 7, 2, 3, 1]

逐层遍历树结构得到数组形式，由于是完全二叉树，不会存在空元素。采用数组来实现堆会更加紧凑，因为根据索引可以直接计算处节点间的关系，而不需要额外存储指针。

一些伪码中的数组常常从 1 开始，所以在实现时要小心处理索引，避免差 1 错误。下面是数组从 1 或 0 开始两种情况下，i 节点的父节点和左右子节点的索引为：

        1       0
parent  i/2    (i+1)/2-1
left    2*i    2*i+1
right   2*i+1  2*i+2

下面是一个实现：

class Heap:
    def __init__(self, data):
        self._data = data
        self.build()

    def __len__(self):
        return len(self._data)

    def __getitem__(self, i):
        return self._data[i]

    def __setitem__(self, i, v):
        self._data[i] = v

    def parent(self, i):
        return ((i+1) >> 1) - 1

    def left(self, i):
        return (i<<1) + 1

    def right(self, i):
        return (i+1) << 1

    def max_heapify(self, i, size):
        l, r = self.left(i), self.right(i)
        lagest = i
        if l < size and self[l] > self[lagest]:
            lagest = l
        if r < size and self[r] > self[lagest]:
            lagest = r
        if lagest != i:
            self[lagest], self[i] = self[i], self[lagest]
            self.max_heapify(lagest, size)

    def build(self):
        for i in range((len(self) >> 1) - 1, -1, -1):
            self.max_heapify(i, len(self))

初始化时传入一个数组，对象维护这个数组
采用特殊方法 __len__, __setitem__ 和 __getitem__ 来操作 self._data，可以简化程序。同时堆对象可以迭代了。
max_heapify 维护了最大堆的性质，它假设左右子树已经是最大堆。
bulid 中调用 max_heapify 构建堆。在初始化时调用。也可以通过后文中的插入方法来构建堆。

堆排序

堆排序利用了堆根元素最大的特点。不断将数组的首位元素交换，然后调用 max_heapify 来重新构建堆。由于是本地排序，排序后的数组便不再是堆了。时间复杂度是 O(nlgn)，空间复杂度是 O(1)。堆排序中数据移动较大，不利于缓存命中。虽然堆排序算法复杂度和快排一样，都是O(nlogn)，性能却没有快排好。

    def sort(self):
        size = len(self)
        for i in range(len(self) - 1, 0, -1):
            self[0], self[i] = self[i], self[0]
            size -= 1
            self.max_heapify(0, size)

优先队列

优先队列是一种抽象的数据结构，其中的每个元素有与之相关的优先级。优先队列通常使用堆来实现，根据堆的不同，优先队列也分为最大优先队列和最小优先队列。基于前面实现的最大堆，这里讨论的是最大优先队列。最大优先队列实现了以下方法：

maximum，获取最大元素，即数组的首元素
extract_max，提取最大元素，交换首尾元素，然后重构堆
increase_key，提升元素的值，可能需要调整堆
insert，新增一个元素。直接加到数组的末尾，然后调用 increase_key

    def maximum(self):
        return self[0]

    def extract_max(self):
        if len(self) == 0:
            raise ValueError("heap empty")
        maxv = self.maximum()
        self[0] = self[-1]
        self._data.pop()
        self.max_heapify(0, len(self) - 1)
        return maxv

    def increase_key(self, i, key):
        self[i] = key
        while i > 0 and self[self.parent(i)] < self[i]:
            self[i], self[self.parent(i)] = self[self.parent(i)], self[i]
            i = self.parent(i)

    def insert(self, key):
        self._data.append(key)
        self.increase_key(len(self) - 1, key)

堆的实现

堆排序

优先队列

参考