最大堆在数组中的表示

1. 简介

在本篇文章中，我们将介绍如何使用数组来表示最大堆（Max Heap）这种数据结构。相比使用显式的二叉树结构，数组实现更加简洁，是实际开发中常用的方式。

最大堆是一种基于完全二叉树的结构，其核心特性是：每个节点的值都不小于其子节点的值。因此，堆顶元素一定是整个堆中的最大值。

2. 数组表示法概览

使用数组表示最大堆时，主要依赖以下两个元素：

elements[]：用于存储堆中所有节点的值
tail：记录堆中最后一个元素的索引。若 tail == 0，表示堆为空

我们假设数组是从 1 开始索引的，也就是说：

堆顶元素位于 elements[1]
对于任意节点 i：
- 左子节点位于 elements[2 * i]
- 右子节点位于 elements[2 * i + 1]
相应地，任意节点 i 的父节点位于 elements[i / 2]（向下取整）

示例

下图是一个最大堆的二叉树表示：

Max heap as a binary tree

我们可以按层序遍历顺序将节点填入数组中：

Levels of the max heap tree

最终数组表示如下：

Mx heap as an array stored level by level

可以看出，数组中的元素是按照从上到下、从左到右的顺序填入的。

3. 最大堆的操作与伪代码

最大堆支持以下核心操作：

插入元素（Insert）
获取最大值（Max）
移除最大值（Remove Max）
构建堆（Heapify）

3.1 插入操作

插入操作将新元素放在数组末尾，然后不断与其父节点比较，若大于父节点则交换，直到堆性质恢复为止。这个过程也称为“上浮”（Heapify Up）。

algorithm INSERT(H, value):
    // INPUT
    //    H = a max heap
    //    value = the value to insert into H
    // OUTPUT
    //    value is added to H, maintaining the max heap property
    
    H.tail <- H.tail + 1
    H.elements[H.tail] <- value
    
    child <- H.tail
    parent <- child / 2
    
    while parent >= 1 and H.elements[parent] < H.elements[child]:
        SWAP(H.elements[parent], H.elements[child])
        child <- parent
        parent <- child / 2

✅ 插入时间复杂度为 O(log n)

3.2 获取最大值

最大值始终位于数组的第一个元素（即 elements[1]），因此获取最大值的时间复杂度为 O(1)。

algorithm MAX(H):
    // INPUT
    //    H = a max heap
    // OUTPUT
    //    Returns the maximal element of H
    
    if H.tail = 0:
        return null
    
    return H.elements[1]

3.3 移除最大值

移除堆顶元素后，将数组最后一个元素移动到堆顶，然后不断与较大的子节点交换，直到堆性质恢复。这个过程也称为“下沉”（Heapify Down）。

algorithm REMOVE(H):
    // INPUT
    //    H = a max heap
    // OUTPUT
    //    The maximum element of H is removed
    
    if H.tail = 0:
        return
    
    H.elements[1] <- H.elements[H.tail]
    H.tail <- H.tail - 1
    
    parent <- 1
    maxChild <- index of parents maximum child or infinity if it has no children
    
    while maxChild <= H.tail and H.elements[parent] < H.elements[maxChild]:
        SWAP(H.elements[parent], H.elements[maxChild])
        parent <- maxChild
        maxChild <- index of parents maximum child or infinity if it has no children

✅ 删除操作时间复杂度为 O(log n)

3.4 构建堆（Heapify）

Heapify 是从数组构建最大堆的过程。它从中间节点开始，逐个向左处理，确保每个子树都满足最大堆性质。

algorithm HEAPIFY(A):
    // INPUT
    //    A = an array to heapify
    // OUTPUT
    //    A max heap H corresponding to array A

    start <- A.size / 2
    for i <- start, start - 1, ..., 1:
        parent <- i
        maxChild <- index of the maximum child of i or infinity if it has no children
        while maxChild <= A.size and A[parent] < A[maxChild]:
            SWAP(A[parent], A[maxChild])
            parent <- maxChild
            maxChild <- index of the maximum child of i 
                        or infinity if it has no children
    
    H <- an empty heap
    H.elements <- A
    H.tail <- H.elements.size
    
    return H

⚠️ Heapify 的时间复杂度为 O(n)，而不是 O(n log n)，因为叶子节点不需要下沉

4. 小结

本文我们介绍了最大堆在数组中的表示方法，以及如何通过数组实现最大堆的插入、删除、获取最大值和构建堆等操作。

数组实现方式简洁高效，非常适合用于实现优先队列等场景。掌握最大堆的数组实现原理，有助于我们更深入地理解堆排序、Top K 问题等经典算法与数据结构问题。

Persistence

REST

Security