# Heapsort

Task: We have to sort an array of some values using Heapsort in Java.

The time complexity of Heap Sort algorithm is O(n * log(n)) as in the average case so in worst and best cases. The essence of heap sort is in finding the maximum value in non-sorted part of the array, putting it to the end of this part and decrementing right bound. Using primitive algorithm for searching maximum value will take O(n) time complexity and repeating it for n elements will take O(n * n). Therefore, we will have to optimize algorithm of searching maximum.
It will be a good idea to use the heap. Heap – is the binary tree with the following characteristics:

1. The tree is balanced (all nodes have the depth of k or k – 1), and the kth level is filled from left to right.
2. Each node has greater value than that of children.

To store heap we will use array, where a is the root, a[i * 2 + 1] and a[i * 2 + 2] are children of a[i] element.
Now we need to build a heap, which will satisfy the conditions above. The right half of array do not have children (because they will be out of bounds), so this part meets conditions. Therefore, we will have to iterate through heap from the middle to the first element and swapping parent and children values if the child is greater than the parent.

For example, we have array {0, 56, 32, 35, 64, 23, 5, 69, 2, 72, 12, 40 }. Elements {0, 56, 32, 35, 64, 23} have children, so let us start. As I mentioned before, we will iterate from the end of this part (element 23). 23 has index 5, so child indices are 5 * 2 + 1 = 11 and 5 * 2 + 2 = 12. However, the maximum index in this array is 11, so 23 has only one child – 40. Since 40 is greater than 23, then we have to swap them. After that array will be {0, 56, 32, 35, 64, 40, 5, 69, 2, 72, 12, 23}. Bold are elements, which were swapped. Underscored are elements to compare on the next iteration. Here are all changes to be made for building the heap: 