在minheap或maxheap上使用時，heapsort更高效嗎？

Question

只是一個一般性的問題....

重申標題：

上minheap使用或maxheap時是堆排序更有效率？

注：使用基於陣列的實現

Answer 1

以下是我對吧，我可能是不正確的，但在這裏不用。理論上講，它們同樣高效。

堆排序的工作原理基本上是將所有元素放入一個（最小）堆中，然後現在它們按堆順序重複刪除最小元素，直到堆爲空，以增加的順序給我們提供數據。它是O（nlogn），因爲我們對數據進行線性傳遞，並且堆支持對數據中每個元素所做的工作進行log n插入/刪除。

如果我們使用最大堆，我們會反覆調用getMax（）。這會產生一個「遞減順序」，但您可以輕鬆地將這些最大值從右到左插入到最終數組中以獲得遞增順序。