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

文章目录

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

前言

在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好，是因为使用向上调整法建堆的时间复杂度为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)