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

Question

我正在做一个来自 Practice Data Structures Final 的练习题

问题

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

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

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

步骤 1、2 和 4 都应该是常数时间。第 3 步应该在 O(log n) 内运行，因为完整树的高度是 log n。所以总的来说，删除的运行时间不应该是 O(log n)

但是，如果您查看答案键(来自链接)，当使用组织为最小堆的数组时，删除的最坏情况渐近运行时间是 O( n).有人可以解释为什么吗？

Answer 1

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

感谢@SotiriosDelimanolis 的评论，我意识到这个问题只涉及堆，而不是遵循特定 ADT(指定数据结构支持的一组值和操作)的堆，如 Priority Queue因此可以从堆中删除任何值。

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

中运行