堆

设想一个使用优先队列的场景，比如管理医院急诊的分诊系统，它不会依照患者来院的顺序治疗，而是根据患者的紧急情况。如果来了个大出血的病患，即便前面有感冒的患者等了很久，也会首先对这个患者进行处理，感冒的患者也必须排到后面。这需要使用优先队列对病患的紧急情况进行排序，情况越紧急，排得越靠前。

现在我们打算用有序数组来实现这个优先队列，对病患的情况从0到9由缓到急进行排列，数值越大越紧急，排得越靠前。目前队列情况如下图。

现在来了位新患者，他的紧急程度是5，我们会把它放到队列中合适的位置，如下图。

需要检查整个数组所有元素才能知道新数据要插入的位置，因此整个有序数组的插入时间复杂度是 $O(n)$。由于原有的元素是有序的，所以这个过程可以用二分查找完成，时间复杂度成了 $O(log \ n)$。在数组中插入数据，需要对后面的数据后挪，在最坏的情况下，在数组最前面插入新数据，原有数据全部都要后挪。

如果紧急程度最高的数据放在左边，删除元素之后，后面的数据得全部往前移。为避免这种情况，可以将数据反过来放置，紧急程度最高的放在右边，从右边删除数据。

用有序数组实现的优先队列，删除数据的时间复杂度是 $O(1)$，插入数据是 $O(log \ n + n)=O(n)$。如果队列中有很多数据，在频繁插入新数据的情况下，$O(n)$ 的时间复杂度会很慢，我们需要一种更高效的数据结构实现优先队列，这种数据结构便是堆。

二叉堆

堆有很多种不同的类型，但这里只讨论二叉堆。堆*(Heap)是一种特殊的完全二叉树。如果父节点大于等于子节点，称为大顶堆(Max Heap)；反之，如果父节点小于等于子节点，称为*小顶堆(Min Heap)。

堆用来一直记录数据集中最大值或最小值的情况。不论是大顶堆还是小顶堆，最顶上的节点必然是最大或最小的，利用这个特点可以实现优先队列抽象数据类型。二叉最大堆和最小堆的思想是一样的，简单起见，这里只讨论二叉最大堆。

满足这两个特点的二叉树才能称为堆：

• 节点值必须大于(等于)或小于(等于)其所有后代节点的值。也称为堆条件。
• 树必须是完全二叉树

下图(a) 是堆，但(b)不是，因为有一个子节点大于父节点，其它子节点都小于父节点。

[!NOTE] 注意

二叉查找树也是一种特殊的二叉树，但二叉查找树不是堆。

完全二叉树从根节点往下，第一层元素个数是$2^0=1$个，第二层$2^1=2$个，第三层$2^2=4$个，第四层$2^3=8$个，除了最后一层，每一层的节点都是满的。完全二叉树缺失的节点只在最后一层的最右边，如果将每一层的元素从上往下，从左往右连起来，全是满的，中间没有空隙。这是为了确保堆的平衡性，二叉树尽可能平衡，树才会尽可能矮，操作效率才会高。

堆主要有两个操作：插入和删除。不像二叉查找树，堆的查找需要访问(检查)每个节点，因此，堆通常不需要实现查找。我们通常只需要它的最大值或最小值，根节点便是最大值或最小值所在。

为了方便后续算法的叙述，我们把最后一层最右边的节点称为尾节点，如下图。

堆的插入

向堆插入新数据有几个步骤： . 将新数据作为尾节点插入堆中。 . 比较新节点和其父节点大小，如果大于父节点，则交换它们的位置。 . 重复步骤2，直到新节点不再大于父节点，或者新节点不再有父节点。

把x作为尾节点插入下图堆中。

与父节点交换位置称为上浮，上浮两次之后符合堆的规则，插入算法结束。

堆的删除

删除根节点有这几个步骤：

1. 用尾节点内容替换根节点，删除尾节点。
2. 把根节点下沉到正确的位置。

堆的删除只删除根节点，不是其它节点。因为根节点要么最大要么最小，这也是使用堆的目的。将根节点与其最大的子节点比较后，如果小于子节点，就交换位置，不断重复这个过程，直至满足堆条件。下图演示了删除的过程。

用数组实现堆

前面的插入和删除算法并未解决查找尾节点的问题，用暴力的遍历方式当然可以查找到尾节点，但这违背了使用堆来实现高效优先队列的初衷。虽然直接使用相互连接节点的方式实现堆也是可能的，但是使用数组实现堆更常见，因为数组查找尾节点很容易。

回顾我们前面讨论的用数组表示二叉树，将树中的元素从上到下，从左往右，依次装入到数组中。堆是一种完全树，也就说明对应的数组元素是一个挨着一个的，元素之间没有空隙，数组最后一个元素就是堆的尾节点。

对于索引 i。

• 查找父节点索引公式：$(i-1)/2$
• 查找左子节点公式：$(i*2)+1$
• 查找右子节点公式：$(i*2)+2$

向堆中插入元素，尾节点上浮，用查找父节点公式确定父节点在数组中的位置。与父节点比较后决定是否需要交换两个元素的位置，不断重复这个过程，直至不再需要交换，此时插入过程结束。

删除数组根节点下沉，需要与最大子节点比较，用查找左右子节点公式确定左右子节点在数组中的位置。与最大的子节点比较后决定是否需要交换两个元素的位置，不断重复这个过程，直至不再需要交换，此时删除过程结束。

以下是大顶堆的简单实现，小顶堆的原理也是相同的。

struct Heap<T> {
    data: Vec<T>
}

/// 大顶堆实现
impl<T: Ord> Heap<T> {
    /// 插入新元素
    fn insert(&mut self, element: T) {
        self.data.push(element);
        let mut tail_index = self.data.len() - 1;
        while tail_index > 0 {
            let parent_index = (tail_index - 1) / 2;
            if self.data[tail_index] > self.data[parent_index] {
                self.data.swap(parent_index, tail_index);
                tail_index = parent_index;
            } else {
                break;
            }
        }
    }

    /// 弹出根节点
    fn pop(&mut self) -> Option<T> {
        match self.data.len() {
            0 => None,
            1 => self.data.pop(),
            _ => {
                let len = self.data.len();
                self.data.swap(0, len - 1);
                let root = self.data.pop();
                Self::max_heapify(&mut self.data, 0);
                root
            }
        }
    }

    /// 将根节点为 index 的子树转换成大顶堆
    fn max_heapify(array: &mut [T], index: usize) {
        let mut root = index;
        while let Some(child) = Self::max_child(array, root) {
            if array[child] > array[root] {
                array.swap(child, root);
            }
            root = child;
        }
    }

    /// 获取最大子节点 index
    fn max_child(array: &[T], parent: usize) -> Option<usize> {
        let left = parent * 2 + 1;
        let right = parent * 2 + 2;
        match (left >= array.len(), right >= array.len()) {
            (true, true) => None,
            (true, false) => Some(right),
            (false, true) => Some(left),
            (false, false) => match array[left] > array[right] {
                true => Some(left),
                false => Some(right),
            }
        }
    }
}

新节点作为尾节点插入到堆中，作为一个元素追加到数组末尾，之后需要和父节点比较，是否交换位置。长度为 n 的数组有$log \ n$层，最多需要比较 $log \ n$ 次，因此，插入元素的时间复杂度是 $O(log \ n)$。

弹出栈顶元素后，尾元素替换作为栈顶元素，之后需要和最大子节点比较是否下沉，最多需要下沉 $log \ n - 1$ 次，因此，删除元素的时间复杂度是 $O(log \ n)$。

不管一维数组还是二维的树，他们都是对逻辑结构的表示。用堆的逻辑在数组上实现优先队列，巧妙地解决了顺序数组需要大量移动数据的问题。