当前位置：首页 > article >正文

【堆排】为何使用向下调整法建堆比向上调整法建堆更好呢？

article 2024/10/9 1:04:15

文章目录

前言
一、堆排代码
一、计算使用==向上调整法==建堆的时间复杂度
二、计算使用==向下调整法==插入的时间复杂度
总结

前言

在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好，是因为使用向上调整法建堆的时间复杂度为O(n*logn)，使用向下调整法建堆的时间复杂度为O(n)。接下来博主就教大家如何计算它们的时间复杂度。

一、堆排代码

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])//若孩子结点比父结点小则交换
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子

	while (child < n)
	{
		//找左右孩子中找最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排
void HeapSort(int* arr, int n)
{
	//向上调整法建堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}

	//向下调整算法建堆
	//for (int i = (n-1-1)/2; i >= 0; i--)
	//{
	//	AdjustDown(arr, i , n);
	//}

	//循环将堆顶数据跟最后位置的数据进行交换
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

一、计算使用向上调整法建堆的时间复杂度

for (int i = 0; i < n; i++)
{
	AdjustUp(arr, i);
}

第1层，2⁰个结点，最多需要向上移动0次。
第2层，2¹个结点，最多需要向下移动1次。
第3层，2²个结点，最多需要向上移动2次。
…
第h-1层，2^h-2个结点，最多需要向上移动h-2次。
第h层，2^h-1个结点，最多需要向上移动h-1次。
所以最多移动的次数总和为：
(1) T(h) = 2⁰(0)+2¹(1)+2²(2)+…+2^h-2(h-2)+2^h-1(h-1)
(2) 2T(h) = 2¹(0)+2²(1)+2³(2)+…+2^h-1(h-2)+2^h(h-1)
(2)-(1) 得
T(h) = -(2¹+2²+2³+…+2^h-2+2^h-1+2^h-1)+2^hh
使用高中阶段学过的等比数列求和公式：S = a1(1-qⁿ)/1-q可得
T(h) = 2(1-2^h)+2^hh = 2+2^h(h-2)
再根据二叉树的性质：n = 2^h-1，h = log₂(n+1)可得
T(n) = 2 + (n+1)(log₂(n+1)-2) = (n+1)log₂(n+1)-2n
所以向上调整法建堆的时间复杂度为O(logn*n)

二、计算使用向下调整法插入的时间复杂度

for (int i = (n-1-1)/2; i >= 0; i--)
{
	AdjustDown(arr, i , n);
}

第1层，2⁰个结点，最多需要向下移动h-1次。
第2层，2¹个结点，最多需要向下移动h-2次。
第3层，2²个结点，最多需要向下移动h-3次。
…
第h-1层，2^h-2个结点，最多需要向下移动1次。
第h层，2^h-1个结点，最多需要向下移动0次。

所以最多移动的次数总和为：
(1) T(h) = 2⁰(h-1)+2¹(h-2)+2²(h-3)+…+2^h-2(1)
(2) 2T(h) = 2¹(h-1)+2²(h-2)+2³(h-3)+…+2^h-1(1)
(2)-(1) 得
T(h) = 2¹+2²+2³+…+2^h-2+2^h-1-2⁰(h-1)
T(h) =2⁰+ 2¹+2²+2³+…+2^h-2+2^h-1-h
使用高中阶段学过的等比数列求和公式：S = a1(1-qⁿ)/1-q可得
T(h) = 2^h-1-h
再根据满二叉树的性质：n = 2^h-1，h = log₂(n+1)可得
T(n) = n-log₂(n+1)*
所以向下调整法建堆的时间复杂度为O(n)