堆的 shift up 学习笔记

什么是堆？

堆是一种树形数据结构，可以用数组来实现。堆的数据结构具有以下性质：

• 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
• 每个节点的左右子树都是一个堆。

其中父节点大于等于子节点的堆叫做“大根堆”，父节点小于等于子节点的堆叫做“小根堆”。

堆的常用操作包括建堆、插入元素、删除元素，其中删除元素又分为删除堆顶元素和删除指定元素。

shift up 的定义

shift up 是向堆中插入元素的操作。当插入一个元素时，需要将其放在堆的最后一个节点，并通过与其父节点比较大小，不断调整位置，直到满足堆的性质为止。这个过程被称为 shift up。

下面是 shift up 的具体实现过程：

pythonCopy Code
def shift_up(heap, index):
    """
    向上调整堆，使其满足堆的性质
    """
    while index > 0:
        parent = (index - 1) // 2  # 获取当前节点的父节点索引
        if heap[parent] < heap[index]:  # 如果父节点小于当前节点，则交换两个节点
            heap[parent], heap[index] = heap[index], heap[parent]
            index = parent  # 将当前节点索引更新为父节点索引
        else:  # 如果父节点大于等于当前节点，则说明堆已经满足性质，跳出循环
            break

shift up 的实例

假设我们有一个空的大根堆，要向其中插入元素 3、5、2、6、4。插入过程如下：

1. 插入元素 3，堆变为 [3]，满足堆的性质。

2. 插入元素 5，堆变为 [3, 5]，不满足堆的性质，需要进行 shift up 操作。

   • 元素 5 与其父节点 3 比较，大于父节点，交换两个节点。堆变为 [5, 3]。
   • 元素 5 大于等于父节点 3，堆满足性质，shift up 结束。

3. 插入元素 2，堆变为 [5, 3, 2]，不满足堆的性质，需要进行 shift up 操作。

   • 元素 2 与其父节点 5 比较，小于父节点，不交换。堆仍为 [5, 3, 2]。
   • 元素 2 与其父节点 3 比较，小于父节点，交换两个节点。堆变为 [5, 2, 3]。
   • 元素 2 大于等于父节点 5，堆满足性质，shift up 结束。

4. 插入元素 6，堆变为 [5, 2, 3, 6]，不满足堆的性质，需要进行 shift up 操作。

   • 元素 6 与其父节点 2 比较，大于父节点，交换两个节点。堆变为 [5, 6, 3, 2]。
   • 元素 6 大于等于父节点 5，堆满足性质，shift up 结束。

5. 插入元素 4，堆变为 [5, 6, 3, 2, 4]，不满足堆的性质，需要进行 shift up 操作。

   • 元素 4 与其父节点 2 比较，大于父节点，交换两个节点。堆变为 [5, 6, 3, 4, 2]。
   • 元素 4 大于等于父节点 6，堆满足性质，shift up 结束。

最终，我们得到的大根堆为 [5, 6, 3, 4, 2]。