Heap sort algorithm Java

Sorting algorithms are used to reorder the elements of an array 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:

• Sorting algorithms – Introduction to data sorting
• Bubble sort
• Comb sort
• Big O notation: analysis of algorithms’ time and space complexity
• Selection sort
• Insertion sort
• Counting sort

Today we will look at sorting using the heap sort algorithm.

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 called a heap. A heap is a complete binary tree with the property that we can find the parents and children of any node using simple arithmetic. 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 at index i is given by (i-1)/2. The root node of the tree has index 0. This index arithmetic allows the input array to represent a complete binary tree without requiring additional memory allocation.

The two special forms of heap are called max-heap and min-heap, and these forms are used in heap sorting. In a max-heap, the value in each parent node is greater than the values of its direct children (one level below) and all indirect descendants (two or more levels below). In a min-heap, the value of a parent node is less than that of its children. For ascending sorting of elements, we use max-heap with the maximum value at the root node, while for descending sorting we use min-heap with the minimum value at the root.

How heap sort works

In the first step, we create a heap from the input array. We transform this into max-heap form using a method called heapify. This method recursively compares parents with their children, swapping values to ensure the largest value moves to the root of the tree. This root value is then swapped with the last leaf node, which is considered sorted and removed from the heap. The heap size is reduced by 1 after each extraction. After swapping the root node, the heap loses its max-heap property, so we must repeat the heapify process. Gradually, as we extract the current maximum values from the tree, the sorting progresses. The algorithm terminates when only one element remains in the heap, which will be the smallest value and belongs at the beginning 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 degrade with larger input sizes

Heap sort disadvantages

• less suitable for sorting small numbers of elements because the overhead of creating and maintaining the heap becomes significant
• Not stable
• Not adaptive

Heap sort time complexity

Heap sort animation, visualization, gif

The heap sort visualization looks like this:

Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

Visit Toptal for interactive visualizations. There are 8 types of algorithms and you can also play the animation backwards.

On this page you can go through the steps of the algorithm to check the time taken by the algorithm.

Heap sort Java code implementation

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 heap sort example is:

We have prepared the files with the above example as code that you can run directly in Java. Download Java Heap Sort code here.

If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers!

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.