Project Technical Lead
Heap sort algorithm Java
Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.
There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.
To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and implement them in Java.
So far, we have discussed the following sorting algorithms:
- Sorting algorithms – introduction to data sorting,
- Bubble sort,
- Comb sort,
- Big O notation-complexity analysis of algorithms,
- Selection sort – sorting by selection,
- Insertion sort – sorting by insertion,
- Counting sort – sorting by counting.
Today we will look at sorting using the heap sort.
Heap sort
Heapsort, created by J. W. J. Williams in 1964, is a relatively popular and very efficient sorting algorithm that stores input data in a data structure calleda heap. A heap is a complete binary tree. It has a very interesting property that we can use to find the parents and children of any node in the tree.This is due to how the heap is constructed from the input array. If the index of any element in the array is i, then the left child will have an index of 2*i+1 and the right child will have an index of 2*i+2. The parent of any element for index i is given by the lower bound (i-1)/2. The root node of the tree has index 0. It is because of this index arithmetic that the input array can be mapped to a full binary tree (heap) and no additional memory allocation is required.
Special forms of heap are called. Max-Heap and Min-Heap and it is these forms that are used in heap-sorting. In a Max-Heap heap, the value in each parent node is greater than the number of its direct (1 level below) and indirect (2 or more levels below the parent) children. In Min-Heap, the value of a parent node is less than that of its children. For ascending reordering of elements, we use Max-Heap with the maximum value of the tree at the root node and for descending reordering we use Min-Heap with the smallest value at the root node.
How heap sort works?
eIn the first step, we create a heap from the input feature vector. We transform this into Max-Heap form, creating a heapify method for this. This will recursively compare the parent and its children, swapping values to ensure that the element with the highest value is moved to the root of the tree. The latter is then exchanged with the last leaf in the tree, and that leaf (with the maximum value) is pruned. This element is considered to be sorted and the heap size is reduced by 1. By swapping the root node, the heap has lost its Max-Heap form and we will have to repeat the whole procedure. Gradually, as we prune the current highest values from the tree, we perform the sorting. The sorting stops when we are left with onlmy one element in the heap that is the smallest and belongs to the top of the array.
Heap sort advantages
- Stable time complexity O(n log n) in all cases,
- does not require additional memory,
- the performance of the algorithm does not decrease with the amount of input data.
Heap sort disadvantages – time, space complexity
- Unsuitable for a small number of elements, the overhead of creating and moving elements in the heap will show,
- is not stable,
- is not adaptive.
Heap sort time requirement
Algorithm | Method | Time complexity | Memory | Stable | ||
worst | average | best | ||||
Heap sort | Selection | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Heap sort animation, visualization, gif
The visualization of the heap sort looks like this:
Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms You can find an animation of the algorithm, for example, at Toptal. There are 8 types of algorithms there, you can also play the animation backwards. On this page you can go through the steps of the algorithm to check the time consumption of the algorithm.
Heap Sort Implementation example step by step – Java code
We will now show the implementation of the Heap sort algorithm in Java. HeapSort.java
package sorting;
public class HeapSort {
public void sort(int data[])
{
// Don't sort if there are no elements
if(data.length == 0)
return;
// Build Max-Heap by rearranging array
for (int i = data.length / 2 - 1; i >= 0; i--) {
heapify(data, data.length, i);
}
// Extract max element from the heap one by one
for (int i = data.length - 1; i > 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
System.out.print("max-heap root node extraction: " + data[i] + " -> ");
printArray(data);
System.out.println("");
// Heapify root node
heapify(data, i, 0);
}
}
// Heapify the subtree by the index i, where n is size of the heap
void heapify(int data[], int n, int i) {
System.out.print("heapify (" + n + ", " + i + ") on ");
printArray(data);
// Find max of (root, left child, right child)
int max = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && data[left] > data[max])
max = left;
if (right < n && data[right] > data[max])
max = right;
// Swap and continue heapifying if root is not max
if (max != i) {
int swap = data[i];
data[i] = data[max];
data[max] = swap;
System.out.println(" => exchange " + data[max] + " for " + data[i]);
heapify(data, n, max);
}
else {
System.out.println(" => no change");
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
//System.out.println();
}
}
Main.java
import sorting.HeapSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
HeapSort heapSort = new HeapSort();
System.out.print("Input: ");
heapSort.printArray(dataToSort);
System.out.println("");
heapSort.sort(dataToSort);
System.out.print("Sorted: ");
heapSort.printArray(dataToSort);
}
}
The output of this example is: We have prepared the above example files in the form of code that you can execute directly in Java. Download Java Heap Sort code. If you’re a Java programmer looking for work, check out our employee benefits and respond to our latest job postings.