算法 之 堆 - 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) 方法可以看到效果

 

更多内容请参考：

算法 之 堆 - 简介

评论

2 楼 flforever1213 2011-03-08  

onewind 写道

恩 heap[0] 保存堆的长度不错，也可以让数组下标从1开始

小弟最近重温算法，多谢支持哈！

1 楼 onewind 2011-03-08  

恩 heap[0] 保存堆的长度不错，也可以让数组下标从1开始