第 4 节 最大堆的第 2 个重要操作：从一个最大堆中取出元素

这个操作叫 sift down。

• 根据堆有序的性质，根结点是堆（数组）中最大的元素，即数组里下标为 1 的元素；
• 从最大堆中取出一个元素，即取出根结点元素，同时还要保持最大堆的性质；
• 根结点取出以后，1 号下标位置为空，于是我们将当前数组的最后一个元素放到 1 号下标的位置。这样做是 因为交换和移动的次数最少，这种想法也是十分自然的，并且保持了完全二叉树的性质；
• 但是此时数组并不满足最大堆的性质，我们就要进行 siftDown 操作使这个数组保持最大堆的性质。

siftDown 的具体操作步骤

从 1 号下标开始，如果存在右孩子，就把右孩子和左孩子比较，比出较大的那个，再和自己比较，如果比自己大，就交换位置，这样的过程直到「不小于两个孩子结点中的最大者」。

同理，我们可以写出 shitDown 的两个版本。

代码实现一：逐层交换下移

说明：

• 当我们从下标 1 开始存放最大堆的元素的时候，最大堆的最后一个元素是 data[count]；
• 在完全二叉树中，如何表示有孩子？其实有左孩子就够了。这里的循环条件是 2 * k <= count ，等于号不能漏掉，自己画一个完全二叉树就清楚了；
• 在结点存在孩子结点的情况下，先判断是否存在右孩子。如果存在右孩子，就一定有左孩子，然后把右孩子和左孩子比较，比出最大的那个，再和自己比较，如果比自己大，就交换位置，这样的过程直到「自己比左右两个孩子都大」为止。

Java 代码：

/**
 * 取出最大堆中的根结点
 * 1、把最后一个元素和下标是 1 的元素进行交换
 * 2、从根结点开始逐层下移：下移的过程中将与左右孩子结点进行比较，把最大的那个跟自己交换
 *
 * @return 根结点的元素
 */
public int extractMax() {
    assert count > 0;
    int ret = data[1];
    swap(data, 1, count);
    count--;
    siftDown(1);
    return ret;
}

/**
* 只要有左右孩子，左右孩子只要比自己大，就交换
*
* @param h
*/
private void siftDown(int h) {
  	// 如果这个元素有左边的孩子
    while (2 * h <= count) { 
        int k = 2 * h;
      	// 如果有右边的孩子，并且还大于左边的孩子，就好像左边的孩子不存在一样
        if (k + 1 <= count && data[k + 1] > data[k]) { 
            k = k + 1;
        }
        if (data[h] < data[k]) {
            swap(data, h, k);
        }
        h *= 2;
    }
}

Python 代码：

def extract_max(self):
    if self.count == 0:
        raise Exception('堆里没有可以取出的元素')
    ret = self.data[1]
    self.data[1], self.data[self.count] = self.data[self.count], self.data[1]
    self.count -= 1
    self.__sift_down(1)
    return ret

def __sift_down(self, k):
    # 只要有左右孩子，左右孩子只要比自己大，就交换
    while 2 * k <= self.count:
        # 如果这个元素有左边的孩子
        j = 2 * k
        # 如果有右边的孩子，大于左边的孩子，就好像左边的孩子不存在一样
        if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
            j = j + 1
        if self.data[k] >= self.data[j]:
            break
        self.data[k], self.data[j] = self.data[j], self.data[k]
        k = j

代码实现二：先暂存，再逐层复制

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

Java 代码：

private void shiftDown(int k) {
    int temp = data[k];
    // 只要它有孩子，注意，这里的等于号是十分关键的
    while (2 * k <= count) {
        int j = 2 * k;
        // 如果它有右边的孩子，并且右边的孩子大于左边的孩子
        if (j + 1 <= count && data[j + 1] > data[j]) {
            // 右边的孩子胜出，此时可以认为没有左孩子，
            j = j + 1;
        }
        // 如果当前的元素的值，比右边的孩子结点要大，则逐渐下落的过程到此结束
        if (temp >= data[j]) {
            break;
        }
        // 否则，交换位置，继续循环
        data[k] = data[j];
        k = j;
    }
    data[k] = temp;
}

Python 代码：

def __sink(self, k):
    # 下沉
    temp = self.data[k]
    # 只要它有孩子，注意，这里的等于号是十分关键的
    while 2 * k <= self.count:
        j = 2 * k
        # 如果它有右边的孩子，并且右边的孩子大于左边的孩子
        if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
            # 右边的孩子胜出，此时可以认为没有左孩子
            j += 1
        # 如果当前的元素的值，比右边的孩子节点要大，则逐渐下落的过程到此结束
        if temp >= self.data[j]:
            break
        # 否则，交换位置，继续循环
        self.data[k] = self.data[j]
        k = j
    self.data[k] = temp

完整代码

Python 代码：

# 通过 LeetCode 第 215 题、第 295 题测试
class MaxHeap:
    def __init__(self, capacity):
        # 我们这个版本的实现中，0 号索引是不存数据的，这一点一定要注意
        # 因为数组从索引 1 开始存放数值
        # 所以开辟 capacity + 1 这么多大小的空间
        self.data = [None for _ in range(capacity + 1)]
        # 当前堆中存储的元素的个数
        self.count = 0
        # 堆中能够存储的元素的最大数量（为简化问题，不考虑动态扩展）
        self.capacity = capacity

    def size(self):
        """
        返回最大堆中的元素的个数
        :return:
        """
        return self.count

    def is_empty(self):
        """
        返回最大堆中的元素是否为空
        :return:
        """
        return self.count == 0

    def insert(self, item):
        if self.count + 1 > self.capacity:
            raise Exception('堆的容量不够了')
        self.count += 1
        self.data[self.count] = item
        # 考虑将它上移
        self.__swim(self.count)

    def __shift_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

    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

    def extract_max(self):
        if self.count == 0:
            raise Exception('堆里没有可以取出的元素')
        ret = self.data[1]
        self.data[1], self.data[self.count] = self.data[self.count], self.data[1]
        self.count -= 1
        self.__sink(1)
        return ret

    def __shift_down(self, k):
        # 只要有左右孩子，左右孩子只要比自己大，就交换
        while 2 * k <= self.count:
            # 如果这个元素有左边的孩子
            j = 2 * k
            # 如果有右边的孩子，大于左边的孩子，就好像左边的孩子不存在一样
            if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
                j = j + 1
            if self.data[k] >= self.data[j]:
                break
            self.data[k], self.data[j] = self.data[j], self.data[k]
            k = j

    def __sink(self, k):
        # 下沉
        temp = self.data[k]
        # 只要它有孩子，注意，这里的等于号是十分关键的
        while 2 * k <= self.count:
            j = 2 * k
            # 如果它有右边的孩子，并且右边的孩子大于左边的孩子
            if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
                # 右边的孩子胜出，此时可以认为没有左孩子
                j += 1
            # 如果当前的元素的值，比右边的孩子节点要大，则逐渐下落的过程到此结束
            if temp >= self.data[j]:
                break
            # 否则，交换位置，继续循环
            self.data[k] = self.data[j]
            k = j
        self.data[k] = temp


if __name__ == '__main__':
    max_heap = MaxHeap(6)
    max_heap.insert(3)
    print(max_heap.data[1])
    max_heap.insert(5)
    print(max_heap.data[1])
    max_heap.insert(1)
    print(max_heap.data[1])
    max_heap.insert(8)
    print(max_heap.data[1])
    max_heap.insert(7)
    print(max_heap.data[1])
    max_heap.insert(12)

    while not max_heap.is_empty():
        print('取出', max_heap.extract_max())

到这里，我们就可以通过「最大堆」实现排序功能了，「最小堆」可以类似地实现。

到此为止，我们已经实现了最大堆的「入队」和「出队」两个基本操作，我们完全通过直接输出元素来检验一下，自己写出的最大堆是否符合最大堆的性质。因为每一次从最大堆取出的总是数组中最大的元素，所以可以将最大堆用于排序。

---

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