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:

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:

heap sort visualization
Nagae, CC BY-SA 4.0, via Wikimedia Commons
heap sort visualization
RolandH, CC BY-SA 4.0, via Wikimedia Commons

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: The output of this example 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.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.

Let us know about you