An intuitive understanding of heapsort?

Question

At school we are currently learning sorting algorithms in Java and I got for my homework the Heap Sort. I did my reading, I tried to find out as much as I could, but it seems I just can't grasp the concept.

I'm not asking you to write me a Java program, if you could just explain to me as simply as you can how the Heap Sort works.

Answer 1

Right, so basically you take a heap and pull out the first node in the heap - as the first node is guaranteed to be the largest / smallest depending on the direction of sort. The tricky thing is re-balancing / creating the heap in the first place.

Two steps were required for me to understand the heap process - first of all thinking of this as a tree, getting my head around it, then turning that tree into an array so it could be useful.

The second part of that is to essentially traverse the tree breadth first, left to right adding each element into the array. So the following tree:

                                    73                          
                                 7      12          
                               2   4  9   10    
                             1          

Would be {73,7,12,2,4,9,10,1}

The first part requires two steps:

1. Make sure each node has two children (Unless you don't have enough nodes to do that as in the tree above.
2. Make sure each node is bigger (Or smaller if sorting min first) than its children.

So to heapify a list of numbers you add each one to the heap, then following those two steps in order.

To create my heap above I will add 10 first - it's the only node so nothing to do. Add 12 as it's child on the left:

    10
  12

This satisfies 1, but not 2 so I will swap them round:

    12
  10

Add 7 - nothing to do

    12
  10  7

Add 73

          12
       10     7
    73

10 < 73 so need to swap those:

          12
       73     7
    10

12 < 73 so need to swap those:

          73
       12     7
    10

Add 2 - nothing to do

          73
       12     7
    10   2

Add 4 - nothing to do

          73
       12     7
    10   2  4

Add 9

          73
       12     7
    10   2  4   9

7 < 9 - swap

          73
       12     9
    10   2  4   7

Add 1 - nothing to do

          73
       12     9
    10   2  4   7
  1

We have our heap :D

Now you just remove each element from the top, swapping in the last element to the top of the tree each time, then re-balancing the tree:

Take 73 off - putting 1 in its place

          1
       12     9
    10   2  4   7

1 < 12 - so swap them

          12
        1    9
    10   2  4   7

1 < 10 - so swap them

          12
       10     9
     1   2  4   7

Take 12 off - replace with 7

          7
       10     9
     1   2  4   

7 < 10 - swap them

          10
       7     9
     1   2  4   

Take 10 off - replace with 4

          4
       7     9
    1   2  

4 < 7 - swap

          7
       4     9
    1   2  

7 < 9 - swap

          9
       4     7
    1   2 

Take 9 off - replace with 2

          2
       4     7
    1   

2 < 4 - swap them

          4
       2     7
    1  

4 < 7 - swap them

          7
       2     4
    1  

Take 7 off - replace with 1

          1
       2     4

1 < 4 - swap them

          4
       2     1

Take 4 - replace with 1

          1
       2

1 < 2 - swap them

          2
       1

Take 2 - replace with 1

          1

Take 1

Sorted list voila.