algorithm - Build a max heap for an array - Stack Overflow

You're building the tree but you're not adjusting your array. The array reflects the heap structure. The first element being the largest element in the array and the following two elements are the left and right child of that one.

The idea is after you build the heap that you swap the last and the first element in the array and then work on the same array but only using the elements 0 ... array.size - 2. The heap-condition is invalid and you call heapify to get a correct heap structure on the smaller array. This gives you again the largest element in that smaller array at the first position. You swap the first and last element in the smaller array and build the heap on the array which has 2 elements less. But you have two elements at the end which are sorted (the biggest element from the whole array and the next biggest element (which is the biggest element from the first smaller array)). You'll do this until you'll have an rest array which has no elements left.

Take a look at Heap Sort diagram in the german wikipedia. First you'll see the unsorted array. The smaller black box indicates the position in the array. The first tree is a heap.

 Unsorted array   23 | 1 | 6 | 19 | 14 | 18 | 8 | 24 | 15     Heapified Array   24 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 15     First iteration   Swap First (Biggest Element in Array) with last Element (could be anything)   15 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 24     heap condition is invalid     Build heap on array.size - 2   23 | 19 | 18 | 15 | 14 | 8 | 6 | 1 || 24     Swap first and last element in smaller heap   1 | 19 | 18 | 15 | 14 | 8 | 6 | 23 || 24     Build heap on array.size - 3   19 | 15 | 18 | 1 | 14 | 8 | 6 || 23 | 24     Swap first and last element on that smaller heap and build heap on array.size - 4   until you cant shrink the heap anymore, you'll receive   || 1 | 8 | 14 | 15 | 18 | 19 | 23 | 24  

The invariant is that your tree is a heap before and after each iteration. That's why it works. Because you'll swap always the largest element to the end of the heapified array.

Read full article from algorithm - Build a max heap for an array - Stack Overflow