【数据结构】——建堆

• 一、堆是什么？
• • 堆(heap)
  • 堆的性质：
  • 堆的分类：
• 二、向下调整算法
• • 1.父子间的关系
  • 2.向下调整算法
  • • step 0：
    • step1
    • step2,3
  • 3.代码展示
• 三，建堆
• • • • 从最后一个父亲节点开始调用，向下调整算法，直到 父亲节点为0截至
      • 代码展示
      • 全部代码展示

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是一棵完全二叉树。

• 堆中某个节点的值总是不大于或不小于其父节点的值。

• 堆中某个节点的值总是不大于或不小于其父节点的值。

将根节点最大的堆叫做最大堆或大顶堆，根节点最小的堆叫做最小堆或小顶堆。常见的堆有二叉堆、斐波那契堆等。

注意事项

void AdjustDown(int* a, int pos, int size)
{
	int parent = pos;
	int node = parent * 2 + 1;   //先默认左节点是两个结点中较大的一个
	while (parent * 2 + 1 < size) //调整过程是一个循环,当找到最后一层，即父节点已经没有子节点的时候，则说明调整完成
	{
		if (node + 1 < size &&  a[node] < a[node + 1] ) //比较左节点和右节点的大小,同时要注意没有右节点的情况
		{
			node = node + 1;   //如果右节点较大，则和parent交换的结点就要变成右节点
		}
		if (a[parent] < a[node])  //判断父结点和子节点的大小，如果子节点大，则交换
		{
			Swap(&a[parent], &a[node]);//交换

			//交换完成后，需要重新定位父节点和子节点
			parent = node;
			node = parent * 2 + 1;
		}
		else
		{
			break;   //如果父节点大，则说明已经整个二叉树已经调整完成了
		}
	}
}

int a[] = { 11,12,34,56,77,89 };
	int size = sizeof(a) / sizeof(a[0]);
	//建堆--大堆
	for(int i=(size-1-1)/2;i>=0;--i)
	{
			AdjustDown(a, i, size);
	}

#include

void Swap(int* a, int* b) //交换函数
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustDown(int* a, int pos, int size)
{
	int parent = pos;
	int node = parent * 2 + 1;   //先默认左节点是两个结点中较大的一个
	while (parent * 2 + 1 < size) //调整过程是一个循环,当找到最后一层，即父节点已经没有子节点的时候，则说明调整完成
	{
		if (node + 1 < size &&  a[node] < a[node + 1] ) //比较左节点和右节点的大小,同时要注意没有右节点的情况
		{
			node = node + 1;   //如果右节点较大，则和parent交换的结点就要变成右节点
		}
		if (a[parent] < a[node])  //判断父结点和子节点的大小，如果子节点大，则交换
		{
			Swap(&a[parent], &a[node]);//交换

			//交换完成后，需要重新定位父节点和子节点
			parent = node;
			node = parent * 2 + 1;
		}
		else
		{
			break;   //如果父节点大，则说明已经整个二叉树已经调整完成了
		}
	}
}
int main()
{
	int a[] = { 11,12,34,56,77,89 };
	int size = sizeof(a) / sizeof(a[0]);
	//建堆--大堆
	for(int i=(size-1-1)/2;i>=0;--i)
	{
			AdjustDown(a, i, size);
	}
	//打印出建好的堆
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	
	return 0;
}

效果展示