我正在处理练习数据结构最终版中的练习题
问题所在
使用保持组织为最小堆的数据结构数组时，查找删除的最坏情况渐近运行时。
我最初的想法是删除操作是 O（log n），因为删除算法是
- 将
- 开始元素与结束元素交换。将结束元素设置为空
- 递减大小
- 将新根渗透到树下
- 返回原始开始元素
步骤 1、2 和 4 都应该是恒定时间。步骤 3 应该在 O（log n） 中运行，因为完整树的高度是 log n。所以总的来说，删除的运行时间不应该是 O（log n）
但是，如果您查看答案键（从链接），则在使用组织为最小堆的数组时，删除的最坏情况渐近运行时间为 O（n）。有人可以解释为什么会这样吗？
来自堆定义 - "二叉树只有在具有堆属性并且是完整树的情况下才是一个堆"
多亏@SotiriosDelimanolis评论，我意识到这个问题仅涉及一个堆，而不是遵循特定 ADT（指定数据结构支持的值和操作集）之后的堆，例如优先级队列，因此可以从堆中删除任何值。
多亏了@PaulHankin的评论，我意识到在堆中查找值已经在 O（n） 中运行，并且移动必要的元素以维护完整的树属性也将在 O（n） 中运行。因此，堆上的此删除操作在 O（n） 中运行