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

什么是堆

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

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

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

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

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

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

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

堆的逻辑结构

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

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

  1. 树中的每个节点都包含一个值,其中每个节点的值大于等于(最大堆)或小于等于(最小堆)其子节点的值。
  2. 树的每一层(除了最后一层)都是满的,最后一层的节点尽量都靠左排列。

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

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

堆的物理结构

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

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

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

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

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

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

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

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

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

swim 操作(上浮)

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

具体过程如下:

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

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 操作将堆的最后一个元素下沉到正确的位置。

具体过程如下:

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

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;
  }
}

堆的完整代码实现

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

主要针对两个操作:

  • 插入元素。将新元素添加到堆的末尾,增加堆的大小并将新元素 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;
    }
}

写在最后

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

发表回复

后才能评论