Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java
communitycreator

How to implement heap sort in Java

Shanzay Gauhar

Heap sort utilizes the heap data structure to perform comparison-based sortingwhere it finds and places the minimum or maximum element at the start based upon ascending or descending order, respectively. Heap sort is an in-place algorithm, i.e., it does not require any additional space.

Algorithm

An array-based representation for the binary heap is space-efficient. Here, if the parent node is at index i, then the left child node is at 2i+1 and the right child is at 2i+2, as shown in the diagram below:

Example of an array based representation of a binary heap

build-max-heap: creates a max heap from an unsorted array.

build-min-heap: creates a min heap from an unsorted array.

This algorithm discusses the sorting of the heap in ascending order; hence, we will build a max heap from the input. The maximum value will reside on the root of the heap.

We will swap the first element, i.e., the largest element with the last element of the heap, and then reduce the size of the heap by 1. Once we have successfully done that, we will call the heapify method for the root of the tree. We will then repeat this step until the size of the heap is greater than 1.

heapify() is similar to build-max-heap/build-min-heap, but comparatively faster due to the assumption made in heapify that some part of the array is already sorted. However, at the very start, we may use the heapify method to build max heap as well. Slight modifications in conditions in the heapify method will enable us to create a min-heap.

Code

class HeapSort{
    void print(int array[],int size){
        int index = 0;
        while(index < size){
            System.out.print(" " + array[index]);
            index++;
        }
    }
    void heapify(int arr[], int size, int index){
        int  maximum = index;
        int leftChild = 2*index + 1;
        int rightChild = 2*index + 2;
        int swapper;

        //now check if right and left child are greater than parent and the right and left child index are not out of bound.
        if(leftChild < size && arr[leftChild] > arr[maximum]){
            maximum = leftChild;
        }
        if(rightChild < size && arr[rightChild] > arr[maximum]){
            maximum = rightChild;
        }

        //if maximum is not equal to its initial declaration(root) then swap.
        if(maximum != index){
            swapper = arr[index];
            arr[index] = arr[maximum];
            arr[maximum] = swapper;

            //we will recursively heapify the affected sub-tree
            heapify(arr,size,maximum);
        }
    }

    void sort(int array[]){
        int size = array.length;
        int swapper;

        //building max heap using heapify
        int index = (size/2) - 1;
        while(index >=0){
            heapify(array,size,index);
            index--;
        }
        
        //We will extract elements from heap one by one and reduce size of the heap (assuming part of array is sorted controlled by index)
        for(index = size -1; index > 0; index--){
            //largest resides on root in max-heap
            swapper = array[0];
            array[0] = array[index];
            array[index] = swapper;

            //call heapify on root of reduced heap
            heapify(array,index, 0);
        }
    }


    public static void main(String args[])
    {
        int array[] = { 3, 1, 4, 9, 8, 6 };
        int size = array.length;
        HeapSort object = new HeapSort();
        object.sort(array);
        System.out.println("After Heap Sort: ");
        object.print(array,size);
    }
}

Time complexity

The time complexity of heap sort is O(nlog(n))O(nlog(n)), where nn is the size of the array.

RELATED TAGS

java
communitycreator
RELATED COURSES

View all Courses

Keep Exploring