二叉堆.md

二叉堆

1. 堆与二叉堆

堆的定义

这里的堆（heap）是数据结构中的堆，而不是内存中的堆模型。

堆通常可以被看成是一棵树，它满足以下性质：

1. 堆中任意节点总是不大于（或者不小于）其子节点的值
2. 堆是一棵完全树

任意节点不大于取子节点的堆叫做最小堆或者小根堆，相反，任意节点不小于取子节点的堆叫做最大堆或者大根堆。

常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。

二叉堆的定义

二叉堆是完全二叉树或者近似完全二叉树，它也分为最大堆和最小堆。

二叉堆一般都通过"数组"来实现。数组实现的二叉堆，父节点和子节点的位置存在一定的关系。有时候，我们将"二叉堆的第一个元素"放在数组索引0的位置，有时候放在1的位置。当然，它们的本质一样（都是二叉堆），只是实现上稍微有一丁点区别。

假设第一个元素在数组中的位置为0的话，则父节点和子节点的位置满足如下关系：

1. 位置为i的左孩子的位置是 2*i+1
2. 位置为i的右孩子的位置是 2*i+2
3. 位置为i的父节点的位置是 floor((i-1)/2)

假设第一个元素在数组中的位置为1的话，则父节点和子节点的位置满足如下关系：

1. 位置为i的左孩子的位置是 2*i
2. 位置为i的右孩子的位置是 2*i+1
3. 位置为i的父节点的位置是 floor(i/2)

注：本文二叉堆的实现统统都是采用"二叉堆第一个元素在数组索引为0"的方式。

2. 二叉堆的添加和删除代码

在前面，我们已经了解到："最大堆"和"最小堆"是对称关系。这也意味着，了解其中之一即可。本节的图文解析是以"最大堆"来进行介绍的。

二叉堆的核心是"添加节点"和"删除节点"，理解这两个算法，二叉堆也就基本掌握了。下面对它们进行介绍。

添加

假设在最大堆[90,80,70,60,40,30,20,10,50]中添加85，需要执行的步骤如下图：

如上图所示，向最大堆中添加数据时：

1. 先将数据插入最大堆的尾部
2. 将该元素向上挪动，直到满足堆的性质为止

代码：

int maxheap[100];
int size = 0;
int capacity = 100;

// 最大堆的向上调整算法
// i：被调节的元素的起始位置（一般为堆中最后一个元素）
void maxheap_filter_up(int i)
{
	int current = i;	//当前节点的位置
	int parent = (current - 1) / 2;	//父节点的位置
	int tmp = maxheap[current];	//当前节点的值
	
	while(current > 0 && maxheap[parent] < tmp)
	{
		// 父节点向下调整，本元素向上调整
		maxheap[current] = maxheap[parent];
		current = parent;
		parent = (current - 1) / 2;
	}
	
	// 到达了合适的位置
	maxheap[current] = tmp;
}

// 将数据插入到堆中
int maxheap_insert(int data)
{
	// 如果堆已满，则返回-1
	if(size == capacity)
		return -1;
	
	maxheap[size] = data; //将数据插入堆的尾部
	maxheap_filter_up(size);	//向上调整堆
	size++;	//堆的实际容量+1
	
	return 0;	
}

删除

假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要执行的步骤如下图所示：

如上图所示，当从最大堆中删除数据时：

1. 先删除该数据，然后用最大堆中最后一个的元素插入这个空位
2. 将该元素向下挪动，直到满足堆的性质为止。

注意，如下图所示的调整方法是不允许的：

因为在调整过程中要始终保证堆为一个完全二叉树。

代码：

// 返回数据在二叉堆中的位置
int get_index(int data)
{
	for(int i = 0; i < size; i++)
	{
		if(data == maxheap[i])
			return i;	
	}
		
	return -1;
}

// 最大堆的向下调整算法
// i：被调节的元素的起始位置
// end：截止范围（一般为堆的尾部位置）
void maxheap_filter_down(int i, int end)
{
	int current = i;	//当前节点的位置
	int left_child = 2 * current + 1;	//节点的左儿子的位置
	int tmp = maxheap[current];	//当前节点的值
	
	while(left_child <= end)
	{
		// 取左右两个孩子中的较大着
		// left_child是左孩子，left_child + 1是右孩子
		if(maxheap[left_child] < maxheap[left_child + 1])
			left_child++;
		
		if(tmp >= maxheap[left_child])
			break;	//调整结束
		
		// 儿子节点向上调整
		maxheap[current] = maxheap[left_child];
		// 本元素向下调整
		current = left_child;
		left_child = 2 * left_child + 1;
			
	}
	
	// 到达了合适的位置
	maxheap[current] = tmp;
}

int maxheap_remove(int data)
{
	// 如果"堆"已空，则返回-1
	if(size == 0)
		return -1;
	
	int index = get_index(data);
	// 找不到该元素
	if(index < 0)
		return -1;
	
	// 用最最后元素填补空缺
	maxheap[index] = maxheap[size-1];
	size--;
	// 从index位置开始自上向下调整为最大堆
	maxheap_filter_down(index, size-1);
	
	return 0;
}

测试

int main()
{
	int a[10];
	// 随机初始化10个值
	init(a, 10);
	
	// 打印原始数据
	for(int i=0; i<10; i++)
		printf("%d ", a[i]);
	printf("\n-------------\n");
	
	// 将原始数据逐个加入堆
	for(int i=0;i<10;i++)
	{
		maxheap_insert(a[i]);
		for(int j=0; j<size; j++)
			printf("%d ", maxheap[j]);
		printf("\n");
	}
		
	// 将堆中的数据从大到小删除
	for(int i=0;i<10;i++)
	{
		maxheap_remove(10-i);
		for(int j=0; j<size; j++)
			printf("%d ", maxheap[j]);
		printf("\n");
	}
	
	return 0;
}

结果：

2 8 5 1 10 9 3 6 7 4 -------------2 8 5 1 10 9 3 6 7 4 2 8 2 8 2 5 8 2 5 1 10 8 5 1 2 10 8 9 1 2 5 10 8 9 1 2 5 3 10 8 9 6 2 5 3 1 10 8 9 7 2 5 3 1 6 10 8 9 7 4 5 3 1 6 2 9 8 5 7 4 2 3 1 6 8 7 5 6 4 2 3 1 7 6 5 1 4 2 3 6 4 5 1 3 2 5 4 2 1 3 4 3 2 1 3 1 2 2 1 1 (null) 请按任意键继续. . .