为何heapq.heappush是O(log n)操作？若新建数组是否应为O(n)？

首先纠正两个关键误解：

1. heapq.heappush不会创建新数组，它直接在传入的列表上原地修改，不存在O(n)级别的数组复制操作。
2. heapq.heapify的时间复杂度是O(n)，不是你注释里写的O(n log n)。

具体执行流程（以小顶堆为例） #

heappush的操作分为两步：

• 第一步：追加元素到列表末尾：把新元素直接加到列表最后，Python列表的append操作是均摊O(1)的时间复杂度。
• 第二步：上浮调整堆结构：将新元素与它的父节点比较，如果新元素更小，就交换两者位置；重复这个过程，直到新元素的父节点比它小（或到达堆顶），此时堆的性质恢复。

堆是完全二叉树结构，其高度为log₂n（n为堆中元素总数）——每一层元素数量翻倍，从最底层到根节点最多需要log₂n次比较和交换，这一步的时间复杂度是O(log n)。

结合你的代码示例来看：
原堆[1,4,2,8,7,3]执行heappush(minHeap, 1)时：

1. 先把1追加到列表末尾，得到[1,4,2,8,7,3,1]；
2. 新元素索引为6，父节点索引是(6-1)//2=2，对应元素是2，1<2，交换后得到[1,4,1,8,7,3,2]；
3. 此时新元素在索引2，父节点是索引0的元素1，两者相等，无需继续交换，操作结束。

整个过程仅进行1次交换，时间复杂度由堆的高度决定，也就是O(log n)。

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