优先队列与堆排序的时间复杂度分析

优先队列其实就是由各种堆实现，最大堆可以实现最大优先队列，最小堆可以实现最小优先队列。
可以参考以下文章：
优先队列(PriorityQueue) - 简书 (jianshu.com)
排序算法-堆排序和时间复杂度_阿巴卡的博客-CSDN博客_堆排序时间复杂度
优先队列(priority queue)_csuzhucong的博客-CSDN博客_优先队列

本文就时间复杂度进行分析：

1. 从一个无序的序列调整成最大堆（最小堆）的形式，时间复杂度为O(n)，理由如下：

该调整方法是从$\frac{n}{2}$开始（可以证明$\frac{n}{2}$是从后往前看第一个非叶子结点），对每个非叶子节点进行下沉操作

某个节点进行下沉操作的时间复杂度与该节点所在的高度成正比（因为需要与它的两个孩子对比，下去之后继续跟两个孩子对比，直至到达叶子节点或者不用下去）

那么总的时间复杂度与 所有非叶子节点的高度之和 成正比

一共$h$层，第$i$层有$2^i$个节点，高度为$h-i$
$$S=2^0\ast h+2^1\ast (h-1)+\cdots +2^i\ast (h-i)+\cdots +2^{h-1}\ast (h-(h-1))$$

S = 2 S − S = 2 1 ∗ h + 2 2 ∗ ( h − 1 ) + ⋯ + 2 h − 1 ∗ ( h − ( h − 2 ) ) + 2 h ∗ ( h − ( h − 1 ) ) − S = − 2 0 ∗ h + 2 1 + ⋯ + 2 h − 1 + 2 h ∗ ( h − ( h − 1 ) ) = − h + 2 h − 2 + 2 h = 2 h + 1 − h − 2

S​=2S−S=21∗h+22∗(h−1)+⋯+2h−1∗(h−(h−2))+2h∗(h−(h−1))−S=−20∗h+21+⋯+2h−1+2h∗(h−(h−1))=−h+2h−2+2h=2h+1−h−2​

由$2^0+2^1+\cdots +2^h=n$可得$h=lo{g}_2(n+1)-1=O(lo{g}_{2}n)$，所以$S=n-lo{g}_2(n+1)-2=O(n)$。

2. 堆排序的时间复杂度为$O(nlo{g}_{2}n)$，理由如下：

以大顶堆为例，分为两部分：

1. 将无序的列表整理成最大堆形式；
2. 把根节点取走，根节点存的就是最大的，用最后一层的最后一个节点代替根节点，然后从对根节点进行下沉操作。循环第2步，直到节点被全部取走。

由于对根节点的下沉操作的时间复杂度与整个堆的高度$h$成正比，而高度$h=O(lo{g}_{2}n)$，其中$n$一直在变，可以发现第二部分的时间复杂度为：
S = l o g 2 n + l o g 2 ( n − 1 ) + ⋯ + l o g 2 1 = l o g 2 ( n ! )

S​=log2​n+log2​(n−1)+⋯+log2​1=log2​(n!)​
可以证明$lo{g}_2(n!)和nlo{g}_{2}n$是同阶函数：
$$\begin{gathered} {\frac{n}{2}}^{\frac{n}{2}}\le n!\le n^n \\ \frac{1}{4}nlog(n)\le \frac{n}{2}log(n^{\frac{1}{2}})\le \frac{n}{2}log(\frac{n}{2})\le n!\le nlog(n) \end{gathered}$$
所以，第二部分的时间复杂度$S=O(nlog(n))$，由于第一部分的时间复杂度为$O(n)$，所以总的时间复杂度为$O(nlog(n))$。