目录
1. 什么是 Shift Down？
Shift Down（下沉）是一种用于堆的维护操作。它通常用于堆的删除操作，特别是当我们移除堆顶元素后，需要通过下沉操作来保持堆的性质。
具体来说，下沉操作会将堆顶元素（通常是最大堆或最小堆中的根元素）与其子节点交换，直到堆顶元素符合堆的性质。
2. Shift Down 的原理
假设我们操作的是最大堆：
- 交换根节点与最后一个节点：首先，将堆的根节点与堆中的最后一个节点交换位置，然后删除最后一个节点。
- 下沉元素：从根节点开始，将交换后的节点与其子节点进行比较，选择较大的子节点，如果当前节点小于较大的子节点，则交换位置。继续下沉，直到节点到达合适的位置或没有子节点。
最大堆示例（删除堆顶元素）：
80
/ \
50 60
/ \ / \
30 40 45 20
删除堆顶元素 80，首先与最后一个元素交换：
20
/ \
50 60
/ \ / \
30 40 45 80
然后进行下沉：
60
/ \
50 45
/ \ / \
30 40 20 80
继续下沉：
60
/ \
50 20
/ \ / \
30 40 45 80
最终，堆恢复了最大堆的性质。
3. Shift Down 的实现
PHP 代码实现
function shiftDown(&$heap, $index, $size) {
while (2 * $index + 1 < $size) {
$left = 2 * $index + 1;
$right = 2 * $index + 2;
$largest = $index;
if ($left < $size && $heap[$left] > $heap[$largest]) {
$largest = $left;
}
if ($right < $size && $heap[$right] > $heap[$largest]) {
$largest = $right;
}
if ($largest == $index) {
break;
}
// 交换
list($heap[$index], $heap[$largest]) = [$heap[$largest], $heap[$index]];
$index = $largest; // 继续向下
}
}
function removeRoot(&$heap) {
$size = count($heap);
$heap[0] = $heap[$size - 1]; // 将根元素与最后一个元素交换
array_pop($heap); // 删除最后一个元素
shiftDown($heap, 0, $size - 1);
}
示例
$heap = [80, 50, 60, 30, 40, 45, 20];
removeRoot($heap);
print_r($heap);
Python 代码实现
def shift_down(heap, index, size):
while 2 * index + 1 < size:
left = 2 * index + 1
right = 2 * index + 2
largest = index
if left < size and heap[left] > heap[largest]:
largest = left
if right < size and heap[right] > heap[largest]:
largest = right
if largest == index:
break
# 交换
heap[index], heap[largest] = heap[largest], heap[index]
index = largest # 继续向下调整
def remove_root(heap):
size = len(heap)
heap[0], heap[-1] = heap[-1], heap[0] # 将根元素与最后一个元素交换
heap.pop() # 删除最后一个元素
shift_down(heap, 0, size - 1)
示例
heap = [80, 50, 60, 30, 40, 45, 20]
remove_root(heap)
print(heap)
4. Shift Down 的时间复杂度
在最坏情况下，Shift Down 需要将根节点下沉到堆的叶节点：
- 堆的高度为
O(log n) - 每次下沉操作交换
O(1)
因此，Shift Down 的时间复杂度为 O(log n)。
5. 应用场景
- 删除堆顶元素：在优先队列中，堆顶元素通常是最小/最大元素，删除堆顶后需要进行 Shift Down 操作以保持堆的性质。
- 堆排序：堆排序过程中，我们不断将堆顶元素移除，并使用下沉操作维护堆结构。
- 实时数据流：维护动态的优先队列时，删除操作往往会涉及 Shift Down。
6. 参考资料
- 《算法导论》第 6 章 – 堆的基本操作
- LeetCode 题解：https://leetcode.cn/tag/heap/
- GeeksForGeeks Heap Operations: https://www.geeksforgeeks.org/binary-heap/
发表回复