coursera公开课关于堆的问题

Questions about heaps in coursera's open course

这里有两题我答错了，但不知道为什么。

1.Suppose 您使用 sorted 数组（例如，从最大到最小）实现优先级队列的功能。 Insert 和 Extract-Min 的最坏情况运行时间分别是多少？（假设你有一个足够大的数组来容纳你面临的插入。）

我的答案是 O(log(n)) 和 O(1) 因为我们可以二分搜索和插入所以 O(log(n))

extract-min 很简单。

但正确答案是 O(n) 和 O(1)。

2.Suppose 您使用 unsorted 数组实现了优先级队列的功能。 Insert 和 Extract-Min 的最坏情况运行时间分别是多少？（假设你有一个足够大的数组来容纳你面临的插入。）

我的答案是 O(1) 和 O(log(n))，因为插入是任意的，提取最小值我们可以先排序然后取最小值。

但正确答案是 O(1) 和 O(n)

谁能帮我解决这个问题？非常感谢。

哦，我明白了第二个问题，排序需要 O(n*log(n)) 而不是 O(log(n))

数组的问题不是找到需要插入元素的地方，而是实际插入它。它将要求您将其旁边的所有元素移动一个索引，这将花费 O(n)。
例如：[1,5,8,10,15]，你需要插入4，找到你需要插入的地方很容易，但是你需要扩展数组（可以通过[=17轻松完成） =]), 然后将所有大于 4 (5,8,10,15) 的元素向右推，这将是 O(n)，你将得到 [1, _, 5, 8, 10, 15] - 所以你可以安全地添加 4不覆盖现有值。
现在，插入一个元素相当容易 - 您只需将它推到数组的后面，它将是 O(1)（使用动态数组）。但是，搜索最小值将需要 linear scan，即 O(n)。

排序后的数组，可以在O(log n)中搜索合适的插入位置，但需要O(n) ] 用于插入。因为你需要把地方后面的所有元素都移动。