目录

  1. 什么是 Shift Up？
  2. Shift Up 的原理
  3. Shift Up 的实现
  4. Shift Up 的时间复杂度
  5. 应用场景
  6. 参考资料
  7. 出站链接

1. 什么是 Shift Up？

Shift Up（上浮）是一种用于堆的维护操作。当向堆中插入一个新元素后，它可能会破坏堆的性质，因此需要向上调整该元素的位置，使得整个堆仍然符合最大堆或最小堆的性质。

2. Shift Up 的原理

假设我们向最大堆中插入一个元素：

  1. 插入元素 到数组末尾（堆的最后一个位置）。
  2. 比较当前节点与其父节点的大小：
    • 如果当前节点比父节点大，则交换位置。
    • 继续向上比较，直到满足堆的性质或到达根节点。

最大堆示例（插入 80）：

      50
     /  \
   30    40
  /  \   /
10   20 35

插入 80 后：

      50
     /  \
   30    40
  /  \   /  \
10   20 35  80  <-- 新插入的元素

通过 Shift Up 交换：

      50
     /  \
   80    40
  /  \   /  \
10   20 35  30

继续交换：

      80
     /  \
   50    40
  /  \   /  \
10   20 35  30

最终，堆重新恢复了最大堆的性质。

3. Shift Up 的实现

PHP 代码实现

function shiftUp(&$heap, $index) {
    while ($index > 0) {
        $parent = floor(($index - 1) / 2);
        if ($heap[$index] <= $heap[$parent]) break;

        // 交换当前节点和父节点
        list($heap[$index], $heap[$parent]) = [$heap[$parent], $heap[$index]];
        $index = $parent; // 继续向上
    }
}

插入元素示例

function insert(&$heap, $value) {
    $heap[] = $value; // 插入到堆的最后
    shiftUp($heap, count($heap) - 1);
}

$heap = [50, 30, 40, 10, 20, 35];
insert($heap, 80);
print_r($heap);

Python 代码实现

def shift_up(heap, index):
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] <= heap[parent]:
            break
        heap[index], heap[parent] = heap[parent], heap[index]
        index = parent  # 继续向上调整

def insert(heap, value):
    heap.append(value)  # 插入到堆的末尾
    shift_up(heap, len(heap) - 1)

# 示例
heap = [50, 30, 40, 10, 20, 35]
insert(heap, 80)
print(heap)

4. Shift Up 的时间复杂度

在最坏情况下，Shift Up 需要一直调整到根节点：

  • 堆的高度为 O(log n)
  • 每次上浮操作交换 O(1)

因此，Shift Up 的时间复杂度为 O(log n)。

5. 应用场景

  • 堆插入操作：在优先队列、Dijkstra 算法中，每次插入新元素都需要 Shift Up 调整堆。
  • 实时数据流：维护Top K 数据时，新的数据可能会破坏堆结构，需要 Shift Up 进行调整。

6. 参考资料

  1. 《算法导论》第 6 章 – 堆的基本操作
  2. LeetCode 题解：https://leetcode.cn/tag/heap/
  3. GeeksForGeeks Heap Operations: https://www.geeksforgeeks.org/binary-heap/

7. 出站链接