Heapsort in Java

Question

So I've been trying to implement this algorithm but I'm not so sure on where to start. Basically from what I understood you can implement it in two ways, by sorting it that the top level is the minimum (minHeap) or that the top level is the max of everything (maxHeap). I googled a lot about any of the two ways and I could not get a grip on how to actually implement it. I do not get the idea in general I would say, can anyone please explain how this works? Like how the minHeap one should work, or the maxHeap one. Thank you in advance!

Answer 1

I'm assuming that you have a basic understanding of binary heap implementation in an array.

Let's say you have an array of integers that you want to sort into ascending order. One way is to rearrange items in the array so that they form a max-heap.

Then, you swap the top item (the largest item in the array) with the last item in the heap, decrease the heap count by 1, and sift the item from the top down into its new place in the heap. At the end, the first item in the array will be the next largest item. You repeat that for every item and your array is sorted.

Let's take a small example. Given the array [4,7,6,1,3,5,2], you rearrange them into a heap using Floyd's algorithm.

for (int i = array.length/2; i >= 0; i--)
{
    siftDown(i);
}

This is an O(n) operation.

When you're done, the array is arranged in a binary heap. In this case, the heap would be [7,4,6,1,3,5,2], or:

       7
     4   6
    1 3 5 2

So, we swap the root item with the last item, giving us: [2,4,6,1,3,5,7]. We decrease the count and sift 2 down to its proper place, giving: [6,4,5,1,3,2,7], or the heap representation:

       6
     4   5
    1 3 2

(I omitted the 7 because we decreased the count. But it's still at the end of the array.)

Again, swap the top item with the last item in the heap: [2,4,5,1,3,6,7], decrease the count, and sift down: [5,4,2,1,3,6,7]:

      5
    4   2
   1 3

If you continue that for the remaining five items in the heap, you'll end up with a sorted array.

The code for this is pretty simple:

int count = array.length-1;
while (count > 0)
{
    swap(array[0], array[count]);
    --count;
    siftDown(0);
}

If you want to do a descending sort, you can either do the above with a max-heap and then reverse the array (an O(1) operation), or you can build a min-heap to start.

The siftDown method just moves the item down to its proper place, following the rules for binary heap construction:

void siftDown(int index)
{
    // Left child is at index*2+1. Right child is at index*2+2;
    while (true)
    {
        // first find the largest child
        int largestChild = index*2+1;
        // if left child is larger than count, then done
        if (largestChild >= count)
        {
            break;
        }
        // compare with right child
        if (largestChild+1 < count && array[largestChild] < array[largestChild+1])
        {
            ++largestChild;
        }

        // If item is smaller than the largest child, then swap and continue.
        if (array[index] < array[largestChild])
        {
            swap(array[index], array[largestChild]);
            index = largestChild;
        }
        else
        {
            break;
        }
}