Python基于heapq实现的堆排序代码整体时间复杂度是多少

问题描述 #

我使用堆相关函数实现数组排序，具体实现代码如下：

import heapq

arr =[-74, 0, -4, 20, 7, 1, -4700, 74, 21, 71000, 87, 400, 9]
print ("原数组: ", arr)
print("")
heapArray = arr
length = len(arr)
heapq.heapify(heapArray)
sortedArray = []

for each in (arr[:length]):
    sortedArray.append(heapq.heappop(heapArray))
    
arr = sortedArray
print ("排序后的数组为:", arr)

上述代码可以完成数组排序，咨询该段代码的整体时间复杂度。

结论 #

这段代码的整体渐进时间复杂度为O(n log n)，n为待排序数组的元素个数，各步骤开销拆解如下：

• heapq.heapify(heapArray) 是原地构建最小堆的操作，Python标准库对该操作做了优化，采用自底向上的下沉调整策略，时间复杂度为O(n)，远低于逐个插入元素建堆的O(n log n)开销。
• 循环执行n次heapq.heappop(heapArray)的总开销为O(n log n)：每次弹出堆顶最小元素后，需要对堆做下沉调整维持堆性质，单次调整的时间和当前堆的高度正相关，最坏为O(log k)（k为当前堆内元素个数）。n次操作的总开销累加为log(n) + log(n-1) + ... + log(1) = log(n!)，通过斯特林公式可近似为O(n log n)，是整个排序逻辑的主导开销。
• 其余操作（数组长度计算、切片、元素追加、打印输出）的时间复杂度均不超过O(n)，属于低阶开销，计算渐进复杂度时可忽略。

注：代码中heapArray = arr是引用赋值，建堆和弹出元素的操作会直接修改原输入数组，如果需要保留原始数组内容需要提前做拷贝，该点不影响时间复杂度计算。

内容的提问来源于stack exchange，提问作者Arian Shaikh