2

    我正在处理来自练习数据结构决赛的练习题

问题

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

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

  1. 将开始元素与结束元素交换。将结束元素设置为空
  2. 减小大小
  3. 将新的根向下渗透到树上
  4. 返回原始开始元素

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

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

4

1 回答 1

3

从堆定义- “如果二叉树具有堆属性并且是完整树，则它只是堆”

感谢@SotiriosDelimanolis 的评论，我意识到这个问题只是一个堆，而不是一个特定 ADT 之后的堆（指定数据结构支持的值和操作集），比如优先级队列，因此可以从中删除任何值堆。

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

于 2015-08-16T19:07:13.527 回答