堆🌟🌟🌟🌟🌟

算法系统课

为了更好的理解堆排序，我们先来掌握堆这种数据结构，掌握堆之后，学习堆排序就很简单了。

什么是堆

在计算机科学中，堆（Heap）是一种非常重要的数据结构，常用于实现优先队列等应用。

堆的高效之处在于它可以实现快速的插入和删除操作，并且在时间复杂度为 O(log n) 的情况下找到最大值或最小值。

堆的概念可能有些抽象，但通过一个简单的例子，我们来更好地理解堆的用途。

在任务管理器中，通常使用堆来存储所有运行中的进程，并根据它们的优先级来调度。

通过堆这种数据结构，操作系统能够快速找到并执行具有 最高优先级 的进程，从而实现高效的进程调度。
当启动了新的进程时，需要将其 快速的插入 到堆中。

而根据最值的不同，堆又可以分为最大堆和最小堆。

下面我们来具体的介绍堆的逻辑结构和物理结构。

堆的逻辑结构

逻辑结构描述了数据结构中元素之间的关系和组织方式，而不考虑实际存储的方式。

堆的逻辑结构是一个完全二叉树，它满足以下条件：

树中的每个节点都包含一个值，其中每个节点的值大于等于（最大堆）或小于等于（最小堆）其子节点的值。
树的每一层（除了最后一层）都是满的，最后一层的节点尽量都靠左排列。

下图所表示的就是一个最大堆了：

可以看到，对于最大堆来说，从某个节点开始往上追溯可以得到一组非递减的元素，从某个节点开始往下追溯可以得到一组非递增的元素。
最小堆也有类似的性质。

堆的物理结构

物理结构描述了数据结构在计算机内存中的存储方式。

堆通常是通过数组来实现的，具体的存储方式如下：

根节点存储在数组的第一个元素（索引为 0）。
对于节点 i，其左子节点存储在索引 2 * i + 1 处，右子节点存储在索引 2 * i + 2 处。

这种数组表示的方式使得堆中元素的存储更加紧凑和高效，同时使得节点之间的关系便于通过索引计算。

通过上图这个例子可以很清楚的看到其实逻辑结构转化为物理结构，就是将二叉树的节点从高到低，到左到右的顺序依次放到数组中。

虽然我们现在已经了解了堆的逻辑结构和物理结构，但是当插入元素和删除最大元素的时候，我们上述所讲的堆所具备的性质很大可能会受到破坏。

下面我们要讲的就是当堆的元素发生变化时，如何维护堆的性质。

不过我们先来学习堆的 swim 和 sink 两种操作。这两种操作是用来维护堆的性质，确保堆在插入和删除操作后依然是一个有效的堆数据结构。

下面的讲解我们以最大堆为例。

swim 操作（上浮）

当向堆中插入一个新元素时，可能会破坏堆的结构，需要调用 swim 操作将新元素上浮到正确的位置。

具体过程如下：

将新元素添加到堆的末尾。
比较新元素和其父节点的大小。如果父节点的值比新元素小，则交换它们。
继续向上比较并交换，直到新元素到达正确的位置或者成为根节点。

swim 操作类似于气泡从水底上升到水面的过程，确保新元素沿着正确的路径上浮到合适的位置，使堆保持有序。

swim 代码实现

private void swim (int i) {
  while (i > 0 && nums[i] > nums[(i - 1) / 2]) {
    swap(i, (i - 1) / 2);
    i = (i - 1) / 2;
  }
}

sink 操作（下沉）

当从堆中删除根节点（最大元素）后，会留下一个空位，需要调用 sink 操作将堆的最后一个元素下沉到正确的位置。

具体过程如下：

将堆的最后一个元素移动到被删除的根节点位置。
比较当前节点和其子节点的大小。选择较大的子节点进行交换。
继续向下比较并交换，直到当前节点到达正确的位置或者成为叶子节点。

sink 操作类似于一个石头从水面掉到水底的过程，通过不断向下调整根节点，使堆重新符合堆性质。

sink 代码实现

private void sink (int i) {
  while (i * 2 <= N - 1) {
    int j = i * 2 + 1;
    j = j + 1 <= N && nums[j] < nums[j + 1] ? j + 1 : j;
    if (nums[i] > nums[j]) {
      break;
    }
    swap(i, j);
    i = j;
  }
}

堆的完整代码实现

掌握了 swim 和 sink 这两种操作之后，下面我们就能很轻易的完成堆性质的维护。

主要针对两个操作：

插入元素。将新元素添加到堆的末尾，增加堆的大小并将新元素 swim 到合适的位置。
删除最大元素。将堆最末尾的元素放到根节点，减小堆的大小并将根节点的元素 sink 到合适的位置。

这两个操作的代码写起来还是很简单的。

class Heap {
    // 存储堆中的元素
    private int[] nums;
    // 记录堆中最后一个元素的索引
    private int N = -1;

    public Heap (int capacity) {
        nums = new int[capacity + 1];
    }

    public int getMax () {
        if (isEmpty()) {
            return Integer.MIN_VALUE;
        }
        return nums[0];
    }

    public int delMax () {
        if (isEmpty()) {
            return Integer.MIN_VALUE;
        }
        int max = nums[0];
        nums[0] = nums[N];
        N--;
        sink(0);
        return max;
    }

    public void push (int e) {
        nums[++N] = e;
        swim(N);
    }

    private void swim (int i) {
        while (i > 0 && nums[i] > nums[(i - 1) / 2]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    private void sink (int i) {
        while (i * 2 <= N - 1) {
            int j = i * 2 + 1;
            j = j + 1 <= N && nums[j] < nums[j + 1] ? j + 1 : j;
            if (nums[i] > nums[j]) {
                break;
            }
            swap(i, j);
            i = j;
        }
    }

    private boolean isEmpty () {
        return N == -1;
    }

    private void swap (int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

写在最后

到这里我们就已经掌握了堆这种高效的数据结构，本来打算把堆排序也一起写完，不过文章就有点长了，我们放到下篇文章吧。