为何删除二叉堆中间节点的时间复杂度并非O(n)+O(log n)？

• 你的理解完全正确。二叉堆是基于数组实现的完全二叉树，它的设计目标是高效处理堆顶元素的插入和删除（时间复杂度O(log n)），但并未针对随机访问中间节点做优化。
• 要删除任意中间节点y，第一步必须先定位它的位置：因为堆没有维护元素的索引映射关系，只能遍历整个堆数组来查找，这一步的时间复杂度是O(n)。
• 找到节点后，执行删除的标准流程是：用堆的最后一个元素覆盖y的位置，接着将这个元素向上（若它的优先级高于父节点）或向下（若它的优先级低于子节点）调整，直至恢复堆的性质，这一步调整操作的时间复杂度是O(log n)。
• 因此，删除堆中间节点的整体时间复杂度为O(n) + O(log n)，由于O(n)是主导项，通常也可简化表述为O(n)。

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