堆排序时间复杂度为,关于堆排序复杂度分析牛客网
Yyds干货库存
@TOC
堆的物理结构(我们所看到的)是一个数组。
heap的逻辑结构(我们想象的)是一棵完整的二叉树。
1.结构化：用数组表示完整的二叉树。
2.有序性：任意节点的关键字是其子树中所有节点的最大值(最小值)。
而在顶部有最大值的叫做大堆。
顶部有最小值的称为小堆。
3.父子节点
因为都是用数组表示的完全二叉树。
数组对应下标。
子下标=父节点下标2 1
右子下标=父节点下标2 2
二、向下调整算法
向下调整算法
以小堆为例，
当左子树和右子树都是小堆时
从根节点开始。
拿孩子小的那个，跟父亲比，比父亲小的就换。
然后向下，此时将子节点分配给父节点。
直到它被传送到叶节点。
2.实现
Void just down (int * a，int n，int root)//向下调整算法——，建立一个小堆。
int parent=root
int child=parent * 2 1；//我们假设左边的孩子是小一点的。
While (child n)//child作为下标小于元素个数，否则数据不存在。
If (a[child 1] a[child] child 1 n)//作为完全二叉树存在。有可能只有左子树，没有右子树。
孩子；//如果左边的孩子比右边的孩子大，就把年纪小的孩子设为右边的孩子。
If (a[child] a[parent])//如果孩子比父亲小，两者将互换
swap(一个[子代]，一个[父代])；
父母=孩子；
子代=父代* 2 ^ 1；
Else//当孩子比父亲大时，循环结束，因为左右子树都是小堆。
打破；
}
第三，堆排序的实现
以桩为例。
如果发现左子树和右子树都不是大堆，就不能直接使用向下调整算法。
可以从最后一个子树开始倒推，做成左右一堆子树。
但是，由于叶节点调优的实际效果，调优是从最后一个非叶子树开始的，这正好由数组下标表示。每减一次，就会到达前一个数的位置。
元素个数是n，最后一个数的下标是n-1，0是8的左子树，8是(n-1-1)/2。
2.分类
以升序为例。
通常情况下，我们应该考虑按照升序使用小桩。
但是会有一个问题。
要建立一个小的堆，我们应该把最小的数放在堆的顶部。这个数字已经选定，然后我们将在剩余的数字中选择这个数字。这时候树的结构已经乱了，必须重建堆来选择下一个数。构建堆的时间复杂度是O(N)
此时时间复杂度为O(N-1) N-2 N-3 N-4。
最后，建立和选择序列的时间复杂度为O (n 2)
其他比较排序效率很低。
因此，我们按照升序使用大桩。
不用改变二叉树本身的结构就可以使用大堆。
将堆的顶部与最后一个数字交换，使最大的数字排在最后。
对第n-1个数再次使用向下调整算法，找到下一个最大的数，与倒数第二个数交换。
直到有许多站。
3.代码实现
Void just down (int * a，int n，int root)//向下调整算法——建立一个大堆。
int parent=root
int child=parent * 2 1；//假设左孩子比左孩子大。
While (child n)//child作为下标小于元素个数，否则数据不存在。
If (a[child 1] a[child] child 1 n)//作为完全二叉树存在。有可能只有左子树，没有右子树。
孩子；//如果左边的孩子比右边的孩子大，就把大一点的孩子设为右边的孩子。
If (a[child] a[parent])//如果孩子比父亲大，则两者会互换
swap(一个[子代]，一个[父代])；
父母=孩子；
子代=父代* 2 ^ 1；
Else//当孩子比父亲小的时候，因为左右子树堆积而结束循环。
打破；
void heapsort(int* a，int n)
int I=0；
for(I=(n-1-1)/2；I-)//(n-1-1)/2从叶节点的前一个父节点开始，
justdown(a，n，I)；//因为它实际上是一个数组，所以每减一就向前调整下标位置。
int end=n-1；
While (end 0)//这将在有多个值时完成。
swap( a[0]，a[end])；//按升序使用大堆。
justdown(a，end，0)；
end-；
第四，时间复杂性
高度计算二叉树的详细图解不太了解。
*堆排序的总时间复杂度为O(Nlog N)**
。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。