算法 之 堆 - Sift-up和Sift-down
1. Sift-up
假定对于某个i>1，H[i]变成了键值大于它父节点键值的元素，这样就违反了堆的特性。我们需要使用Sift-up运算把新的数据项移到在二叉树中适合它的位置上。
Sift-up的运算沿着从H[i]到根节点的唯一一条路径，把H[i]移到适合它的位置上。在沿着路径的每一步上，都将H[i]键值和它父节点的键值H[?i/2?]相比较。
?
过程 ?Sift-up
输入 ?数组H[1...n]和位于1和n之间的索引i
输出 ?上移H[i]（如果需要），以使它不大于父节点
?
算法描述
done ← false
if i = 1 then exit {节点i为根}
repeat
?? ?if key(H[i]) > key(H[?i/2?]) then 互换H[i]和H[?i/2?]
?? ?else done ← true
?? ?i ←??i/2?
until i = 1 or done
?
注意这里算法描述的数组的索引都是1...n，而不是大家习惯的0...n-1。
// heap[0]用来存储数组中堆数据的长度，堆数据heap[1]...heap[heapLength]// 所以数组的实际长度是heapLength+1，我们只对从数组索引为1开始的heapLength个数据进行操作void siftUp(int* heap, int index){int heapLength = heap[0];if (index < 1 || index > heapLength)return;bool done = false;while(!done && index > 1){if (heap[index] > heap[index / 2]){int temp = heap[index];heap[index] = heap[index / 2];heap[index / 2] = temp;}else{done = true;}index /= 2;}}?
2. Sift-down
假定对于i ≤??n/2?，存储在H[i]中元素的键值变成小于H[2i]和H[2i+1]中的最大值（如果2i+1存在的话），这样也违反了堆的特性。Sift-down运算使H[i]“渗”到二叉树中适合它的位置上，沿着这条路径的每一步，都把H[i]的键值和存储在它子节点（如果存在）中的两个键值里最大的那个相比较。
?
过程 ?Sift-down
输入 ?数组H[1...n]和位于1和n之间的索引i
输出 ?下移H[i]（如果需要），以使它不小于子节点
?
算法描述
done ←?false
if?2i > n?then?exit?{节点i是叶子}
repeat
?? ?i ← 2i
?? ?if i + 1 ≤ n and key(H[i+1]) > key(H[i]) then i ← i + 1
?? ?if?key(H[?i/2?]) <?key(H[i])?then?互换H[i]和H[?i/2?]
?? ?else?done ←?true
?? ?end if
until?2i > n?or?done
?
注意这里算法描述的数组的索引也都是1...n，而不是大家习惯的0...n-1。
// heap[0]用来存储数组中堆数据的长度，堆数据heap[1]...heap[heapLength]// 所以数组的实际长度是heapLength+1，我们只对从数组索引为1开始的heapLength个数据进行操作void siftDown(int* heap, int index){int heapLength = heap[0];if (index < 1 || index * 2 > heapLength)return;bool done = false;while(!done && index * 2 <= heapLength){index *= 2;if (index + 1 <= heapLength && heap[index + 1] > heap[index])index += 1;if (heap[index] > heap[index / 2]){int temp = heap[index];heap[index] = heap[index / 2];heap[index / 2] = temp;}else{done = true;}}}?
我使用的数组是这样定义的：
const int HEAP_LENGH = 10;int heap[HEAP_LENGH + 1] = { HEAP_LENGH, 20, 3, 9, 10, 11, 4, 5, 3, 7, 5 };// 这个数组用 siftDown(heap, 2) 方法可以看到效果?
更多内容请参考：
算法 之 堆 - 简介
1 楼 onewind 2011-03-08 恩 heap[0] 保存堆的长度不错，也可以让数组下标从1开始 2 楼 flforever1213 2011-03-08 onewind 写道恩 heap[0] 保存堆的长度不错，也可以让数组下标从1开始