Is heapsort more efficient when used on a minheap or maxheap?

Question

Just a general question....

Reiterating the title:

Is heapsort more efficient when used on a minheap or maxheap?

NOTE: Using an array-based implementation

Answer 1

The following is my take on it, and I could be incorrect, but here goes. In theory, they're equally efficient.

Heap Sort works basically by placing all elements into a (min)heap and then, now that they're in heap order, repeatedly removing the minimum element until the heap is empty, giving us the data in increasing order. It's O(nlogn) since we do linear passes through the data, and the heap supports a log n insertion/removal for the work that we do for each element in the data.

If we used a max heap, we'd be repeatedly calling getMax(). This produces a "decreasing order" but you can easily insert these max values from right to left in your final array to get an increasing order.