使用Python 3的heapq.heappop弹出所有元素的时间复杂度分析

你一开始可能会觉得堆排序的时间复杂度是 O(Nlog(N))（这里N是堆中元素的总数），但咱们可以从堆的层级操作来拆解它的实际计算过程：

在最坏情况下，堆排序的弹出操作可以分层来看：

• 前N/2次弹出操作，每个元素的筛选调整需要 log(N) 时间（这一步相当于把堆的高度降低了一层）
• 接下来的N/4次弹出操作，每个元素的筛选调整需要 log(N)-1 时间
• 再往后的N/8次弹出操作，每个元素的筛选调整需要 log(N)-2 时间
• ……
• 直到最后一批（N/(2^log(N))次）弹出操作，每个元素的筛选调整需要 log(N) - 堆的当前高度 时间

把这些步骤的时间开销加起来，就形成了这样一个级数：
N/2*(log(N)) + N/4*(log(N)-1) + N/8*(log(N)-2) + … + N/(2^log(N))*(log(N) - 堆的高度)

这个级数最终求和后依然收敛到 O(NlogN)，但这种分层分析能让你更清晰地看到堆排序在每一步的时间开销分布~

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