向上调整&向下调整算法

目录

AdjustUp向上调整

AdjustDown向下调整

AdjustUp向上调整

前提是：插入数据之后，除去插入的数据其他的数据还是为堆

应用：插入数据。

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

性质：

• parent=(child-1)/2 
• leftchild=parent*2+1
• rightchild=parent*2+2

结束循环条件：child > 0

时间复杂度：O(logN) -- 高度次（后面细讲）

//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while ( child > 0 )//此刻parent已经数组越界
	{
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else//child>=parent
		{
			break;
		}
	}
}

AdjustDown向下调整

 向下调整算法有一个前提：左右子树必须是一个堆，才能调整

应用：删除数据。删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

现在我们给出数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

性质：

• parent=(child-1)/2 
• leftchild=parent*2+1
• rightchild=parent*2+2

结束循环条件：child < size (❌child+1 < size && child <size)

时间复杂度：O(logN)-- 高度次（后面细讲）

int array[] = {27,15,19,18,28,34,65,49,25,37};

Adjustdown(php->a, php->size, 0);
//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{
	//假设法
	int child = parent * 2 + 1;
	while (child < size )//why child < size && child+1<size
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//比较
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else//>=
		{
			break;
		}
	}
}

//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

下篇重点： 

• 建堆（方式/时间复杂度）
• 堆排序
• ToK问题 

🙂感谢大家的阅读，若有错误和不足，欢迎指正！