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:
- The tree is balanced (all nodes have the depth of k or k – 1), and the kth level is filled from left to right.
- 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:
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
/** * javagists.com * */ public class HeapSort { public static void main(String[] args) { int[] a = { 0, 56, 32, 35, 64, 23, 5, 69, 2, 72, 12, 40 }; printArray(heapSort(a)); } public static void printArray(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } public static int[] heapSort(int[] array) { // Creating heap int middle = array.length / 2 - 1; for (int i = middle; i >= 0; i--) { int leftChild = array[i * 2 + 1]; // If there is not right child it will be equal to left child int rightChildren = array[i * 2 + (i * 2 + 2 < array.length ? 2 : 1)]; // "Sift" current element if it is less than one of its children if (array[i] < Math.max(leftChild, rightChildren)) { array = sift(i, array, array.length); } } // Sorting array // Right bound of unsorted part of array int rightBound = array.length; while (rightBound > 0) { // Changing positions of the first and the last elements array = swap(0, rightBound - 1, array); rightBound--; // Sifting new first element considering decremented right bound array = sift(0, array, rightBound); } return array; } public static int[] sift(int index, int[] array, int rightBound) { // Iterate while element has at least one child while (index * 2 + 1 < rightBound) { int leftChild = array[index * 2 + 1]; int rightChild = array[index * 2 + (index * 2 + 2 < rightBound ? 2 : 1)]; // If left child is bigger than left and current element we need to // swap current with left child and go to the next iteration if (leftChild >= rightChild && leftChild > array[index]) { array = swap(index, index * 2 + 1, array); index = index * 2 + 1; continue; } // If right child is greater than current - swap and go to the next if (rightChild > array[index]) { array = swap(index, index * 2 + 2, array); index = index * 2 + 2; continue; } // Since we got here, current element is bigger than it children, so we // don't need to iterate more break; } return array; } // Change positions of two elements with indicies i1 and i2 in array public static int[] swap(int i1, int i2, int[] array) { int temp = array[i1]; array[i1] = array[i2]; array[i2] = temp; return array; } } |
