運行堆排序的時間，當所有元件是相同的

Question

我們可以說的是，當所有元素的尺寸的陣列相同的n然後運行堆排序的時間爲O（n）

- >如果這是這種情況，是O（n）堆排序的最佳情況運行時間

Answer 1

當所有元素相等時，構建堆佔用O（n）個步驟。因爲當一個比較O（1）後元素被添加到堆中時，我們看到它處於正確的位置。

刪除根目錄也是O（1），當我們交換尾部和根目錄時，heap屬性仍然滿足。

所有元素都被添加到O（n）中的堆中，並在O（n）中被刪除。所以，在這個的情況下，heapsort是O（n）。我想不出一個更好的情況，所以heapsorts最好的情況必須是O（n）。

'heapsorts best case is O（n）'意思是英文的意思是：存在大小爲n的數組，使得heapsort至多需要對k * n進行排序。這在理論上很好，但在實踐中，它並沒有多說好多快或多快。