Sift Up 和 Sift Down

在这节课中，我们将详细介绍堆（Heap）中的两个关键操作：Sift Up（上浮）和 Sift Down（下沉）。这两个操作是堆排序、堆插入和堆删除过程中非常重要的操作，能够帮助我们维持堆的性质。接下来我们将详细讲解它们的作用、实现和时间复杂度。

1. Sift Up（上浮）

Sift Up（上浮）操作也叫“上浮操作”，用于将一个新插入的元素从堆的底部“上浮”到正确的位置，以保持堆的性质。上浮操作通常出现在插入新元素的过程当中。

1.1 Sift Up的作用

当我们向堆中插入一个新的元素时，首先将该元素放置到堆的最后一个位置（即数组的末尾）。然后，通过上浮操作，我们将这个新插入的元素与父节点进行比较。如果新元素大于父节点（对于最大堆），就交换它们的位置。这样反复进行，直到新元素不再比父节点大或者它成为根节点。

1.2 上浮的实现过程

上浮操作的核心是通过不断与父节点交换位置，直到堆的性质得到恢复。假设在最大堆中，父节点的值大于子节点的值。对于一个给定的元素，我们会比较它和它的父节点，若它的值更大，则交换二者的位置。然后继续检查新的位置的父节点，直到该元素不再比父节点大，或者它成为根节点。

1.3 Sift Up的时间复杂度

Sift Up的时间复杂度是 O(log n)，因为我们最多需要比较并交换的次数等于堆的高度，而堆的高度为log n。

2. Sift Down（下沉）

Sift Down（下沉）操作用于维护堆的性质，通常出现在删除堆顶元素的过程中。当我们删除堆顶元素时，为了保持堆的结构和性质，我们将堆的最后一个元素移动到堆顶，并使用下沉操作来恢复堆的性质。

2.1 Sift Down的作用

在最大堆中，堆顶的元素是最大的元素，删除堆顶元素时，我们需要从堆中移除它。为了保持堆的完全二叉树结构，我们会将最后一个元素放到堆顶的位置。此时，堆可能不再满足堆的性质，因此我们需要通过下沉操作来将这个元素移动到合适的位置。

在下沉过程中，我们将当前节点与它的左右子节点进行比较。选择其中较大的子节点（在最大堆中）与当前节点交换位置。然后继续对被交换的子节点执行下沉操作，直到堆的性质恢复。

2.2 下沉的实现过程

下沉操作的核心是将一个元素和它的子节点进行比较，确保它比左右子节点小（在最大堆中）。如果不是，它会和子节点交换位置，直到堆的性质得到恢复。

2.3 Sift Down的时间复杂度

Sift Down操作的时间复杂度也是 O(log n)，因为在最坏的情况下，我们可能需要遍历堆的每一层，从根节点一直下沉到叶子节点，这需要log n的时间。

3. Sift Up 和 Sift Down 的对比

两者的核心区别是：Sift Up操作是在堆插入过程中使用，而Sift Down操作通常用于堆删除或调整时。

4. Java代码实现

接下来，我们将通过Java代码来演示如何实现Sift Up和Sift Down操作。

4.1 Sift Up实现代码

public class Heap {
    private int[] heap;
    private int size;

    public Heap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 插入元素，并进行上浮操作
    public void insert(int value) {
        if (size == heap.length) {
            System.out.println("Heap is full");
            return;
        }
        heap[size] = value;   // 将元素放在堆的最后位置
        int current = size;
        size++;

        // 上浮操作
        while (current > 0 && heap[current] > heap[parent(current)]) {
            // 如果当前元素大于父节点，交换它们
            swap(current, parent(current));
            current = parent(current);   // 更新当前元素的位置
        }
    }

    // 获取父节点索引
    private int parent(int index) {
        return (index - 1) / 2;
    }

    // 交换两个元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

在这个例子中，我们在insert方法中实现了上浮操作。每次插入新元素后，我们都会检查新元素和其父节点的关系，必要时进行交换，直到堆的性质得到恢复。

4.2 Sift Down实现代码

public class Heap {
    private int[] heap;
    private int size;

    public Heap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 删除堆顶元素，并进行下沉操作
    public int remove() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int root = heap[0];  // 获取堆顶元素
        heap[0] = heap[size - 1];  // 将堆的最后一个元素放到堆顶
        size--;
        siftDown(0);   // 从堆顶开始进行下沉操作
        return root;
    }

    // 下沉操作
    private void siftDown(int index) {
        int leftChild = leftChild(index);
        int rightChild = rightChild(index);
        int largest = index;

        // 比较左子节点和右子节点，选择最大值
        if (leftChild < size && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }
        if (rightChild < size && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }

        // 如果当前节点不是最大节点，交换并继续下沉
        if (largest != index) {
            swap(index, largest);
            siftDown(largest);  // 递归下沉
        }
    }

    // 获取左子节点索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // 获取右子节点索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }

    // 交换两个元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

在remove方法中，我们首先将堆顶元素删除并替换为堆的最后一个元素。然后，我们通过 siftDown方法将堆顶元素下沉，恢复堆的性质。

5. 总结

在堆的操作中，Sift Up和Sift Down是两个非常重要的操作，它们能够帮助我们在插入和删除元素时维护堆的性质。Sift Up操作用于插入新元素时保证堆的结构，而Sift Down操作则用于删除堆顶元素时恢复堆的结构。这两个操作的时间复杂度均为O(log n)，它们是实现堆排序、优先队列等数据结构和算法的基础。

通过对这两个操作的深入理解，我们可以更好地应用堆这种数据结构，并在实际问题中充分发挥堆的优势。