堆排序时间复杂度
新能源开发-民用机场
2023年3月20日发(作者：凉粉的做法)【堆排序】堆排序的两种建堆⽅法
buildMaxHeap⽅法
buildMaxHeap⽅法的流程简单概括起来就是⼀句话，从/2⼀直到根结点进⾏maxHeapify调整。下⾯是图解。
Java代码
publicstaticvoidmaxHeapify(int[]a,inti,intlength)
{
intl=left(i);
intr=right(i);
intlargest=i;
while(true)
{
if(la[i])
largest=l;
if(ra[largest])
largest=r;
if(i!=largest)
swap(a,i,largest);
else
break;
i=largest;
l=left(largest);
r=right(largest);
}
}
publicstaticvoidbuildMaxHeap(int[]a)
{
for(inti=/2;i>=0;i--)
maxHeapify(a,i,);
}
运⾏时间分析
粗粗来看前⾯buildmaxheap的时间复杂度，每次maxHeapify调整需要的时间为lg(n),总共要遍历的元素有N/2个，所以⼤致的运⾏时间复杂度为O(nlgn).
如果我们更进⼀步分析，会发现它的实际情况会更理想⼀点。⾸先⼀个，我们从第/2个元素开始执⾏maxHeapify，最开始这⼀层的元素只有⼀个⼦结
点，也就是说，就算要调整，顶多⼀次就搞定了，不需要⾛lgn这么多步。
要做进⼀步的分析，我们可以先思考⼀下我们要建的这个完全⼆叉树堆的⼏个特性。以如下图为例：
我们看这棵⼆叉树，它必须保证每⼀层填满之后才能去填充下⼀层。⽽且，如果从根结点开始计数，往下第i层的元素如果不是最后⼀层的话，这⼀层的元素数量为
2**i(2的i次⽅)。这样，对于⼀棵⾼为h的⼆叉树，它的所有结点数⽬就等于前⾯完全填满的层元素加上最下⾯⼀层的元素。
为什么要把他们分开来计数呢？是因为最下⾯⼀层的元素有⼀个变动的范围，作为⼀棵⾼度为h的树，最下⾯⼀层的元素最少可以是1，最⼤可以是把整层填充满，
也就是2**(h+1)。这样，他们求和的结果就是最少为2**h，最⼤为2**(h+1)。
所以假设堆的元素数量为n的话，我们就可以推出：
结合这⼀步分析，我们可以得到:h<=lgn 结论1： 我们可以发现⼀个n个元素的树，它的⾼度相当于logn（向下取整）。 我们再来看我们分析的第⼆个结论。对应树每⼀个⾼度的⼀层，该有多少个元素呢？假设⾼度为1的那⼀层他们的元素个数为k，那么他们的访问时间复杂度为O(k)。 根据前⾯的分析，我们还发现⼀个情况，就是如果从根结点开始计数，往下第i层的元素如果不是最后⼀层的话，这⼀层的元素数量为2**i(2的i次⽅)。正好这个第i层就 相当于树的总⾼度减去当前层的结点的⾼度。假设第i层的⾼度为h，那么也就是i=lgn-h。 结论2： 这⼀层的元素数量为： 那么他们所有元素的运算时间总和为如下： 根据如下公式： 则有： 现在，我们发现，buildMaxHeap⽅法的时间复杂度实际上为O(n). maxHeapInsert⽅法 maxHeapInsert⽅法和前⾯的办法不⼀样。它可以假定我们事先不知道有多少个元素，通过不断往堆⾥⾯插⼊元素进⾏调整来构建堆。 它的⼤致步骤如下： 1.⾸先增加堆的长度，在最末尾的地⽅加⼊最新插⼊的元素。 2.⽐较当前元素和它的⽗结点值，如果⽐⽗结点值⼤，则交换两个元素，否则返回。 3.重复步骤2. 这个过程对应的代码实现如下： Java代码 publicvoidheapIncreaseKey(inti,intkey)throwsException { if(key thrownewException("newkeyissmallthancurrentkey"); a[i]=key; while(i>0&&a[parent(i)] { swap(i,parent(i)); i=parent(i); } } publicvoidmaxHeapInsert(intkey)throwsException { heapSize++; a[heapSize-1]=_VALUE; heapIncreaseKey(heapSize-1,key); } 这⾥的parent()⽅法是⽤来求当前结点的⽗结点。详细的实现可以参考后⾯附件⾥的代码。 这⾥，我们也可以分析⼀下插⼊建堆的时间复杂度。我们先看最理想的情况，假设每次插⼊的元素都是严格递减的，那么每个元素只需要和它的⽗结点⽐较⼀次。 那么其最优情况就是n。 对于最坏的情况下，每次新增加⼀个元素都需要调整到它的根结点。⽽这个长度为lgn。那么它的时间复杂度为如下公式： 这样，插⼊建堆的时间复杂度为nlgn。 总结 常⽤的建堆⽅法主要⽤于堆元素已经确定好的情况，⽽插⼊建堆的过程主要⽤于动态的增加元素来建堆。插⼊建堆的过程也常⽤于建⽴优先队列的应⽤。这些可以 根据具体的时间情况来选取。