Introduction to Heap Sort In Java
Heapsort in Java is a comparison based sorting technique, where data structure Binary Heap is used. This sorting is almost the same as that of selection sort, where the largest element will be selected, and places in the end, and the process will be repeated for all the elements. In order to understand Heap Sort, let us see what Binary Heap Sort in Java.
- Tree-based Data Structure.
- Complete Binary Tree.
- It can have up to two children.
- Value in the root node can be greater(Max Heap) or Smaller (Min Heap)
How does Heap Sort work in Java?
Before moving to the algorithm, let us see what Heapify is.
Heapify
After a heap is created with the input data, the heap property may not be satisfied. To achieve it, a function called heapify will be used to adjust the heap nodes. If we want to create a max heap, the current element will be compared with its children, and if the value of children is greater than the current element, swapping will be done with the largest element in a left or right child. Similarly, if min-heap needs to be created, swapping will be done with the smallest element in the left or right child. For Example, The following is our input array,
We can consider this as a tree instead of an Array. The first element will be the root; the second will be the left child of the root; the third element will be the right child of the root, and so on.
In order to transform the heap into a tree, traverse the tree in a bottom-up direction. Since the leaf nodes do not have children, let us look into the next level. i.e. is 5 and 7.
We can begin at 5 as it is on the left. Here, 5 has two children: 9 and 4, where 9 is greater than the parent node 5. To make parents larger, we will swap 5 and 9. After swapping, the tree will be as shown below.
Let us move to the next element, 7, where 8 and 2 are the children. Similar to the elements 9 and 4, 7 and 8 will be swapped as in the below tree.
Finally, 3 has two children-9 and 8, where 9 is greater among the children and root. So, swapping of 3 and 9 will be done to make the root greater. Repeat the process until a valid heap is formed, as shown below.
Algorithm for Heap Sort in Ascending Order
- Create a Max Heap with the input data
- Replace the last element with the largest element in the heap
- Heapify the Tree
- Repeat the process until the array is sorted
Algorithm for Heap Sort in Descending Order
- Create a Min Heap with the input data
- Replace the last element with the smallest element in the heap
- Heapify the Tree
- Repeat the process until the array is sorted
Now, let us try to sort the above-obtained Heap in ascending order using the given algorithm. First, remove the largest element. i.e. root and replace it with the last element.
Now, heapify the tree formed and insert the removed element in the last of the array, as shown below.
Again, remove the root element, replace it with the last element and Heapify it.
Insert the removed element to the vacant position. Now you can see that the end of the array is being sorted.
Now, Remove element 7 and replace it with 2.
Heapify the tree, as shown below.
Repeat the process until the array is sorted. Removing element 5.
Heapifying the tree.
Removing element 4.
Heapfying again.
At last, a sorted array like this will be formed.
Examples
Now, let us see the source code of Heap Sort in Java
//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call heapify until a heap is formed
heapify(array, i, 0);
}
}
// Heapify function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild = 2*i + 1; // index of left child = 2*i + 1
int rightChild = 2*i + 2; //index of right child = 2*i + 2
// left child is greater than root
if (leftChild < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If largestelement is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.out.println("Input array is: " + Arrays.toString(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.out.println("Sorted array is : " + Arrays.toString(array));
}
}Output
Conclusion
Heap Sort is a sorting technique that depends on the Binary Heap Data structure. It is almost similar to selection sort and does not use separate arrays for sorting and heap.
Recommended Articles
This has been a guide to Heap Sort in Java. Here we discuss the working, Sorting Algorithm with Ascending and Descending Order and examples with sample code. You can also go through our other suggested articles to learn more –
