第 3 节 最大堆的第 1 个重要操作：SiftUp

从这一节开始，我们做的入队操作和出队操作，其实本质上都是在维护堆的定义，这件事情也叫 保持了循环不变量。

向一个「最大堆」中添加元素，对应优先队列中「入队」操作，同时还要保持「最大堆」的性质，即根元素是「最大堆」中最大的元素，即：除了根结点以外任意一个结点不大于它的父亲结点，这个操作叫做 siftUp。

因此，向「最大堆」中的添加元素的时候，我们首先添加在数组的末尾，然后进行调整，使得调整后的数组仍然满足最大堆的性质（这样的操作，移动的次数最少）。

具体步骤如下：

• 新加的元素放在数组的末尾；
• 新加入的元素调整元素的位置：只与它的父结点比较（不必与兄弟孩子比较），如果比父结点大，就交换位置。否则就可以停止了，这个元素就放在当前位置。

重点理解：为什么我们要在数组的末尾添加一个元素呢？可不可以在开头、中间？

• 这是因为在数组的末尾添加元素，时间复杂度为 ，否则要让数组中一部分的元素逐个后移，因此在数组的末尾加入元素是最自然的想法；
• 在数组的末尾添加了一个元素以后，此时的数组就不满足堆的定义（不是堆有序）。我们需要进行一系列的操作，去维护堆的定义（性质）。

如何维护堆的定义和性质？

通过 siftUp 操作把新添加的元素放置到合适的位置；

• 在数组的最后位置添加一个元素，新加入的元素只和父结点比较大小（无需和它的兄弟结点比较）；

• 只要比父结点大（严格大于），就往上走，否则停止；

• 这个新添加的元素就放置在了合适的位置，同时也调整了部分元素的位置；

• 循环这样做，这样的过程叫做 siftUp，siftUp 在《算法（第 4 版）》里面也叫 swim，是「上浮」的意思。

动画理解

大家可以在这个 网页 (opens new window) 上操作一下，体会插入一个元素以后，如何保持堆有序。

代码实现一：基本实现，即逐层「交换」上移

Java 代码：

public void insert(int item) {
    assert count + 1 <= capacity;
    // 把新添加的元素放在数组的最后一位，对应于最大堆最后一个叶子结点
    data[count + 1] = item;
    count++;
    // 考虑将它上移
    siftUp(count);
}

private void siftUp(int k) {
    int temp = data[k];
    // 有下标就要考虑下标越界的情况，已经在下标 1 的位置，就没有必要上移了
    while (k > 1 && data[k / 2] < temp) {
        data[k] = data[k / 2];
        k /= 2;
    }
    data[k] = temp;
}

private void swap(int[] data, int index1, int index2) {
    int temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;
}

Python 代码：

def insert(self, item):
    if self.count + 1 > self.capacity:
        raise Exception('堆的容量不够了')
    self.count += 1
    self.data[self.count] = item
    # 考虑将它上移
    self.__sift_up(self.count)
    
def __sift_up(self, k):
    # 有索引就要考虑索引越界的情况，已经在索引 1 的位置，就没有必要上移了
    while k > 1 and self.data[k // 2] < self.data[k]:
        self.data[k // 2], self.data[k] = self.data[k], self.data[k // 2]
        k //= 2

说明：

• 有交换操作；
• 有下标访问就必须要考虑下标是否越界边界问题，就是这里说的 k > 1。因为当 k = 1 的时候，元素已经在堆顶， siftUp 操作没有意义。

代码实现二：通过逐层赋值

和「插入排序」的优化一样，先存一下这个可能会上移的元素，通过逐层赋值，实现与逐层交换上移等价的操作。

Java 代码：

private void siftUp(int k) {
    // 有下标就要考虑下标越界的情况，已经在下标 1 的位置，就没有必要上移了
    while (k > 1 && data[k / 2] < data[k]) {
        swap(data, k / 2, k);
        k /= 2;
    }
}

// swap(int[] data, int index1, int index2) 代码实现与上同。

• for 循环实现，只是写法不一样

Java 代码：

private void siftUp(int count) {
    for (int k = count; k >= 1 && data[k] > data[k / 2]; k /= 2) {
        swap(data, k, k / 2);
    }
}

Python 代码：

def __swim(self, k):
    # 上浮，与父结点进行比较
    temp = self.data[k]
    # 有索引就要考虑索引越界的情况，已经在索引 1 的位置，就没有必要上移了
    while k > 1 and self.data[k // 2] < temp:
        self.data[k] = self.data[k // 2]
        k //= 2
    self.data[k] = temp

siftUp 是 insert 的一个子过程，有了 siftUp ，insert 函数就可以很快写出来 ：

---

作者：liweiwei1419 链接：https://suanfa8.com/priority-queue/sift-up 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。