關於coursera的開放課程中的堆的問題

Question

這裏有兩個問題，我得到了錯誤的答案，但我不知道爲什麼。

1.假設您使用排序的數組（例如，從最大到最小）實現優先級隊列的功能。 Insert和Extract-Min的最壞情況運行時間分別是多少？ （假設你有足夠大的數組來容納你所面對的插入）

我的答案是O（log（n））和O（1），因爲我們可以二進制搜索並插入O（log（n ））

extract-min很容易。

但正確的答案是O（n）和O（1）。

2.假設您使用未排序的數組實現優先級隊列的功能。 Insert和Extract-Min的最壞情況運行時間分別是多少？ （假設你有一個足夠大的數組來容納你所面對的插入）

我的回答是O（1）和O（log（n）），因爲插入是任意的，並且extract-min我們可以先排序然後取最小值。

，但正確的答案是O（1）和O（n）的

誰能幫我解決這個問題？非常感謝。

---

哦，我明白了第二個問題，排序需要O（N *的log（n））不爲O（log（n））的

Answer 1

1. 與陣列的porblem不是找到你需要插入元素的地方，它實際上是插入它。它將要求你將一個索引旁邊的所有元素移位，這將花費O(n)。
   例如：[1,5,8,10,15]，你需要插入4，找到你需要插入的地方很容易，但是你需要展開數組（可以用dynamic arrays來實現），然後推送所有大於4的元素（5， 8,10,15）右邊，這將是O(n)，你會得到[1, _, 5, 8, 10, 15] - 所以你可以安全地添加4而不會覆蓋現有的值。插入一個元素相當容易 - 你只需要將它推到數組的後面，它會是O(1)（使用動態數組）。但是，搜索最小值需要linear scan，即O(n)。

Answer 2

對於排序後的數組，你可以搜索正確的地方插入O（log n）的，但它需要爲O（n）插入。因爲您需要在地點後移動所有元素。

Answer 3

1. 您需要在插入的值後移動數組中的值，因此O（n）。
2. 你已經指出。排序需要O（n * logn），但您可以使用線性掃描來查找最小值 - O（n）