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[0] 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:

 

Step 1

 

Step 2

 

Step 3
Step 4

 

Step 5

 

Step 6

 

Step 7

 

Heapsort
Step 8

 

Heapsort step 9
Step 9
Heapsort Step 10
Step 10
Heapsort Step 11
Step 11

Now we are ready to sort this array. Maximum value is on the top of the heap, so it is the first element in the array. It must be at the end of the sorted array, so let us swap the last one with the first one.
To find next maximum element we have to move right bound of unsorted part of the array one position left and not to consider right part (sorted array) at all. “Sifting” means changing positions of current element with the greatest of its children while the element is less than at least one of its children. Because of “sifting” new first element through the heap, we will get next maximum element on the top (remember, that the last element is not in the heap now). Now we can move the first item to the end of the unsorted array.
We have to repeat those actions until only one element left in the unsorted part of the array. You can do the same steps with the last item too, but it will have no reason because all elements with greater value are already in their positions, so the first element is the smallest, and it does not need to be swapped.
Here is the code with comments:

Leave a Reply