堆的特殊实现（向下调整算法）

堆的特殊实现（向下调整算法）

目录

什么是堆

 向下调整算法

 如何实现

 实现代码

---

什么是堆

堆是数据结构中的一种完全二叉树，其性质：堆中某个节点的值总是不大于（大堆）或不小于（小堆）其父节点的值   如下示例

 向下调整算法

（前提）左右子树都是小堆才能实现

例如下面给出的数组 int a[] = {27,15,19,18,28,34,65,49,25,37};

逻辑上看做一颗完全二叉树

 

 如何实现

向下调整算法的实现

1、选出左右孩子中小的那一个（15）

2、小的这个孩子跟父亲比
a、如果小的孩子比父亲小，则跟父亲交换，并且把原来孩子的位置当成父亲继续往下调整。直到p走到叶子节点

b、如果小的孩子比父亲大，则不需要处理，调整完成，整个树已经是小堆

 实现代码

#include
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDownward(int*a ,int n, int parent)
{
	int child = parent * 2 + 1;
	//比较两个(左右)孩子的大小
	while (child < n)//在数组下标范围内比较
	{
		//选出左右孩子较小的那个
		if (child+1 < n && a[child+1] < a[child])//假如没有右孩子chile可能越界
		{
			child++;//右孩子比左孩子小 ++child加到右孩子下标
		}
		//parent和较小的孩子交换
		//较小的孩子比父亲小交换，比父亲大跳出（此时已经是小堆）
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
		
	}
}

int main()
{
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int n = sizeof(a) / sizeof(a[0]);
      	AdjustDownward(a,n,0);
	return 0;
}