堆的 Shift Down 操作详解：从最大堆中取出元素

堆的 Shift Down 操作详解：从最大堆中取出元素 | 极客日志

堆的 Shift Down 操作详解：从最大堆中取出元素

1. 堆的删除操作概述

在堆数据结构中，我们通常只能删除堆顶元素（最大堆中的最大值或最小堆中的最小值）。删除堆顶元素后，我们需要重新调整堆结构以维持堆的性质，这个过程称为'下沉'（Shift Down）操作。

2. Shift Down 操作原理

Shift Down 操作的基本步骤：

将堆顶元素（最大值）取出
将堆的最后一个元素移动到堆顶
将这个新堆顶元素逐步向下比较和交换，直到找到合适的位置

Shift Down 过程图示

初始最大堆结构：

 62
/ \
52 30
/ \ / \
41 28 22 13
/ \
19 16

对应的数组表示：[null, 62, 52, 30, 41, 28, 22, 13, 19, 16]

第一步：取出堆顶元素 62

交换堆顶 (62) 和最后一个元素 (16) 的位置：

 16
/ \
52 30
/ \ / \
41 28 22 13
/ \
19 62

数组状态：[null, 16, 52, 30, 41, 28, 22, 13, 19, 62]

移除最后一个元素 (62)，count 减 1

第二步：开始 Shift Down 操作

第一次比较：16 与其子节点 52 和 30 比较（52 > 30）

16 < 52，需要交换
 52
/ \
16 30
/ \ / \
41 28 22 13
/
19

数组状态：[null, 52, 16, 30, 41, 28, 22, 13, 19]

第二次比较：16 的新位置，与其子节点 41 和 28 比较（41 > 28）

16 < 41，需要交换
 52
/ \
41 30
/ \ / \
16 28 22 13
/
19

数组状态：[null, 52, 41, 30, 16, 28, 22, 13, 19]

第三次比较：16 的新位置，与其子节点 19 比较

16 > 19？不，16 < 19，需要交换
 52
/ \
41 30
/ \ / \
19 28 22 13
/
16

数组状态：[null, 52, 41, 30, 19, 28, 22, 13, 16]

第四次比较：16 已经是叶子节点，Shift Down 结束

最终堆结构：

 52
/ \
41 30
/ \ / \
19 28 22 13
/
16

3. Java 实现代码

/**
 * 从最大堆中取出一个元素
 */
public class HeapShiftDown<T extends Comparable<T>> {
    protected T[] data;
    protected int count;
    protected int capacity;

    // 构造函数，构造一个空堆，可容纳 capacity 个元素
    public HeapShiftDown(int capacity) {
        // 索引 0 不使用，所以需要 capacity+1 的空间
        data = (T[]) new Comparable[capacity + 1];
        count = 0;
        this.capacity = capacity;
    }

    // 返回堆中的元素个数
    public int size() {
        return count;
    }

    // 返回一个布尔值，表示堆中是否为空
    public boolean isEmpty() {
        return count == 0;
    }

    // 向最大堆中插入一个新的元素 item
    public void insert(T item) {
        assert count + 1 <= capacity;
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    // 从最大堆中取出堆顶元素
    public T extractMax() {
        assert count > 0;
        T ret = data[1]; // 取出最大值
        swap(1, count); // 交换堆顶和最后一个元素
        count--; // 元素数量减 1
        shiftDown(1); // 对新的堆顶元素进行 shift down
        return ret;
    }

    // 获取最大堆中的堆顶元素
    public T getMax() {
        assert count > 0;
        return data[1];
    }

    // 交换堆中索引为 i 和 j 的两个元素
    private void swap(int i, int j) {
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     * 最大堆核心辅助函数 - 上浮操作
     * @param k 要进行上浮操作的元素的索引
     */
    private void shiftUp(int k) {
        while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    /**
     * 最大堆核心辅助函数 - 下沉操作
     * @param k 要进行下沉操作的元素的索引
     */
    private void shiftDown(int k) {
        while (2 * k <= count) { // 当前节点有左孩子
            int j = 2 * k; // 初始设为左孩子
            // 如果有右孩子且右孩子比左孩子大
            if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0)
                j++; // 选择较大的孩子
            // 如果当前节点大于等于较大孩子，停止下沉
            if (data[k].compareTo(data[j]) >= 0)
                break;
            swap(k, j); // 否则交换当前节点与较大孩子
            k = j; // 继续向下检查
        }
    }

    // 测试 HeapShiftDown
    public static void main(String[] args) {
        HeapShiftDown<Integer> heap = new HeapShiftDown<Integer>(100);
        int N = 10; // 堆中元素个数
        int M = 10; // 堆中元素取值范围 [0, M)
        // 插入随机元素
        for (int i = 0; i < N; i++)
            heap.insert(new Integer((int) (Math.random() * M)));
        Integer[] arr = new Integer[N];
        // 依次取出最大值
        for (int i = 0; i < N; i++) {
            arr[i] = heap.extractMax();
            System.out.print(arr[i] + " ");
        }
        // 验证结果是否有序
        for (int i = 1; i < N; i++)
            assert arr[i - 1] >= arr[i];
    }
}

4. 代码解析

extractMax 方法：
- 取出堆顶元素（最大值）
- 交换堆顶和最后一个元素
- 减少计数器
- 调用 shiftDown 调整堆结构
shiftDown 方法：
- 循环条件：当前节点有子节点（2*k <= count）
- 找出较大的子节点（比较左右子节点）
- 如果当前节点小于较大子节点则交换
- 更新当前节点索引为较大子节点索引
- 继续循环直到满足堆性质
辅助方法：
- swap：交换两个位置的元素
- shiftUp：插入元素时使用的上浮操作
- getMax：获取但不删除堆顶元素

5. 时间复杂度分析

Shift Down 操作的时间复杂度同样取决于树的高度。因为堆是完全二叉树，所以高度为 O(log n)，其中 n 是堆中元素的数量。因此，Shift Down 操作的时间复杂度为 O(log n)。

6. 实际应用

Shift Down 操作在以下场景中非常重要：

堆排序：通过不断取出堆顶元素实现排序
优先队列：实现优先级最高的任务先出队
图算法：如 Dijkstra 算法中高效获取最小距离节点
事件驱动模拟：按时间顺序处理事件

7. 总结

Shift Down 操作是堆数据结构中最核心的操作之一，它与 Shift Up 操作共同保证了堆的性质。理解 Shift Down 的运作机制对于掌握堆及相关算法至关重要。通过本文的图示和代码示例，读者应该能够清晰地理解 Shift Down 的整个过程及其实现方式。

堆的 Shift Down 操作详解：从最大堆中取出元素