为什么最小堆删除的最坏情况运行时实现为数组 O(N)？

Question

我正在做一道来自 Practice Data Structures Final

的练习题

问题

找到最坏情况下的渐近 运行 使用数据结构数组保持组织为最小堆时的删除时间。

我最初的想法是删除操作是O(log n)因为删除的算法是

1. 将开始元素与结束元素交换。将结束元素设置为 null
2. 减小大小
3. 沿着树向下渗透新根
4. Return 原始开始元素

第一步、第二步、第四步都应该是常数时间。第 3 步应该 运行 in O(log n) 因为完整树的高度是 log n。所以总的来说，删除的运行时间不应该是O(log n)

但是，如果您查看答案键（来自 link），使用组织为最小堆是 O(n)。有人可以解释为什么吗？

Answer 1

来自 Heap Definition - “只有当二叉树具有堆 属性 并且是一棵完整的树时，它才是一个堆”

感谢@SotiriosDelimanolis 的评论，我意识到这个问题只是指堆，而不是遵循特定 ADT（指定数据结构支持的值和操作集）的堆，例如 Priority Queue 所以它可以从堆中删除任何值。

感谢@PaulHankin 的评论，我意识到在堆中找到一个值已经 运行 在 O(n) 并将必要的元素转移到在 O(n) 中维护完整的树 属性 也会 运行。因此，在 O(n)

中对堆 运行s 执行此删除操作