1

我正在审查决赛并偶然发现以下问题：

二叉堆默认具有优先级队列语义：如果我们将某个元素插入 n 次，则需要在它“消失”之前将其移除 n 次。想象一下，你想用集合语义来实现二进制堆。在这种情况下，插入和删除操作的速度有多快？

(a) 插入：O(n) 删除：O(logn)

(b) 插入：O(log n) 删除：O(n)

(c) 插入：O(log n) 删除：O(log n)

(d) 插入：O(1) 删除：O(n2)

(e) 以上都不是。

要插入使用优先队列语义实现的堆，它将是 O(logn)，删除也是如此。但是对于集合，插入和删除取决于集合本身的许多因素。你认为答案应该是什么？

4

2 回答 2

2

目前尚不清楚集合语义指的是什么，但作者可能指的是属性

A ∪ {x} ∪ {x} = A ∪ {x}

即添加一个已经在集合中的元素应该没有（可观察的）效果。

一种直接的方法是在插入时检查重复项。然而，在正常的二叉堆中，删除任意元素需要 O(n)，这显然相当慢。

一个更聪明的想法可能是在删除最小元素时消除重复，通过重复删除直到我们看到一个新值。这需要 O(k log n)，其中 k 是检索到的节点的重复数。如果已知 k 是常数，则为 O(log n)。但在最坏的情况下，k = n，使得最坏情况的时间复杂度为 O(n log n)。但是，如果我们改为测量摊销时间复杂度，则该算法的插入和删除时间为 O(log n)。

通过使用平衡二叉搜索树而不是堆，可以实现插入和删除的最坏情况时间复杂度 O(log n)。不过，这是否符合“堆”的条件尚不清楚。

总而言之，可能的答案是：

  • O(n), O(log n) : 有点幼稚的堆
  • O(log n), O(n log n) : 调整真实堆，最坏情况时间复杂度
  • O(log n), O(log n) : 调整真实堆，摊销时间复杂度
  • O(log n), O(log n) : 伪装成堆的平衡二叉搜索树

也就是说，根据我们如何解释问题，不同的答案是正确的。

于 2016-12-18T03:28:45.333 回答
2

我会说插入：O（n）删除：O（log n）。不允许在集合中重复项，应忽略插入重复项的尝试，因为堆是完全填充的二叉树（底部除外），如果要插入到集合中，请搜索（项目）如果你找到它，你什么都不做插入，所以插入可能需要 O(n) 来查找和插入（你最多可能会渗透到 log n 次）。deleteMin 的时间复杂度为 o(log n)

于 2016-12-18T02:20:43.563 回答