Python中heapq实现getMaxUnit函数的时间复杂度分析疑问

1. heapq.heappop 操作的时间复杂度本质 #

Python标准库heapq的底层是基于顺序数组实现的最小化完全二叉堆，每个节点的左右子节点位置可以通过下标直接计算，不需要额外的指针存储开销。

• 单次heappop的执行逻辑非常明确：首先把堆顶（也就是堆中优先级最高的元素）和堆数组的最后一个元素做交换，把数组长度减1，把原来的堆顶元素“移出”堆结构；之后从新的堆顶位置开始做下沉调整：逐次和当前节点的子节点比较大小，交换不满足堆约束的节点，一路向下直到节点到达叶子层、所有父子关系都符合堆要求为止。
• 因为完全二叉堆的总高度固定为⌊log₂m⌋（m是当前堆里的元素总数），整个下沉调整只需要沿着根到叶子的单条路径做比较交换，不需要遍历堆里的所有节点，所以单次heappop的时间复杂度是O(log m)，这里的m就是执行这次弹出操作时，堆里实际剩下的元素数量。
• 很多人会误以为堆调整是线性操作，实际上每次pop只需要走最长的那一条树高路径，单步的代价远低于全堆遍历的线性开销。

2. 逐段推导getMaxUnit的整体时间复杂度 #

（1）边界判断段 #

开头直接判断truckSize == 0 or num == 0就返回0，是常数级的判断操作，开销O(1)，不会拉高整体复杂度。

（2）堆构建段 #

• 首先循环num次，每次往初始列表里append一个元组(-1*unitPerBox[i], boxes[i])，因为要把最大单位数的盒子放到堆顶，所以用负号做了大顶堆的模拟。这部分循环是线性遍历，总开销O(num)。
• 接着调用heapq.heapify(h)把这个无序列表转成合法堆：注意这个接口不是逐个元素插入堆，而是从下往上批量做堆调整，总时间复杂度是O(n)（n就是列表长度，这里等于num），比逐个heappush的O(n log n)效率高很多。

（3）循环弹出计算段 #

循环的退出条件有两个：一是卡车剩余容量小于0，二是堆已经被全部清空。

• 最坏的情况下，要把堆里的所有num个元素依次弹出来：第一次pop的时候堆里有num个元素，开销是O(log num)；第二次pop的时候堆里剩num-1个元素，开销是O(log(num-1))；一直到最后一次pop的时候堆里只剩1个元素，开销是O(log 1)。
• 把所有这些单次pop的开销加总，相当于计算log num + log(num-1) + ... + log 1，也就是log(num!)，根据斯特林公式可以推导得出，这个累加和的量级是O(num log num)。
• 循环内部的容量扣减、余量判断、累计最大可装容量这些操作，都是单次常数级的算术计算，每轮循环的额外开销不随输入规模增长，不会提升整体复杂度的量级。

小提示：原函数定义里UnitSize参数重复写了两次，属于代码笔误，不影响复杂度的推导结论。

3. 最终复杂度结论 #

• 最优场景：直接触发开头的边界判断返回，时间复杂度O(1)。
• 最坏场景：完整弹出堆里的所有元素完成计算，整体取各部分开销的最高量级，最终时间复杂度为O(num log num)。

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