In what order does a minheap sort?

Question

I've been reading various definitions on minHeap and maxHeap. I stumbled upon statements which say:

1. minHeap is used to sort in descending order.
2. maxHeap is used to sort in ascending order.

Statements taken from the "Note" in https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/ . But when I implement minHeap using PriorityQueue<Integer> in Java with default comparator, and poll() it, I get the minimum element. Why is that? Thanks to anybody who's trying to help :).

Answer 1

min-heap and max-heap don't sort. You can use a min-heap or max-heap to sort, but in standard use, heaps aren't sorted. Instead, they arranged in what's called heap order. This arrangement makes it efficient to add items, and to remove the smallest (or largest) while keeping the data in the proper order.

For example, here's an illustration of a min-heap:

                1
            3       2
          4   7   6   5

That follows the rule that no child is smaller than its parent. The resulting array representation of that heap is [1,3,2,4,7,6,5]. Note that there are other valid heaps with those same numbers. For example, both of the below are valid, as well:

                1                          1
            2       5                  2       3
          4   3   6   7              4   5   6   7

The corresponding array representations are [1,2,5,4,3,6,7] and [1,2,3,4,5,6,7].

Max-heap is similar, except the rule is that no child can be larger than its parent.

The Wikipedia article on binary heap explains this all very well.

Now, when you're talking about using heap sort, you build a heap and then repeatedly swap the root element with the last element in the array, reduce the count and then re-heapify. So you build the sorted array from back to front. If you use a min-heap, then the root (smallest value) will be at the end of the array.

So if you want to sort in descending order with heap sort, you use a min-heap.