Thursday, January 17, 2019

Heap Sort Program in Java

In this post we’ll see how to write Heap sort program in Java. Heap sorting is done using the heap data structure so it is important that you know about heap and how to implement a heap data structure before going to heap sort program.


Heap data structure

Heap is a tree based data structure consisting of nodes and edges. Nodes represent the values stored in the data structure and edges (lines) connect the nodes. To get from one node to another you will follow the path along these edges. Following figure shows a conceptual representation of a tree structure.

tree structure

Heap data structure is represented as a binary tree; binary tree is a tree where each node can have maximum of two children. Head data structure is a complete binary tree meaning it is filled in. Last node may not be full (may not have both children) where as in full binary tree each parent node has both children.

Types of heap

There are two representations of heap structure-

  • Max heap
  • Min heap

Max heap- In max heap value of parent node is greater than the values of its child nodes. So root node is always the maximum element.

Min heap- In min heap value of parent node is smaller than the values of its child nodes. So root node is always the smallest element.

heap data structure

Heap data structure creation in program

Heap data structure is usually represented by an array. When you have an array with its elements it is considered as a complete binary tree. Following figure shows the conceptual representation of a complete binary tree along with the array indexes for the array - {3 10 1 14 6 8}

complete binary tree

When a tree is represented as an array you can find the parent or children of any node using the following equations.

For a node at index i in the array-

  • Parent node is – (i-1)/2
  • Left child node is- 2*i + 1
  • Right child node is- 2*i+2 (or left child +1)

You will use these equations in your program to traverse to children of a node or to traverse to a parent.

Creating heap from tree

This complete binary tree structure has to be transformed to a heap data structure so that every parent node value is greater than its child node values (in case of max heap). The process is commonly known as “heapify”.

In order to create a heap we’ll have to start from the nodes at the bottom and move upwards comparing if child node is greater than the parent and swapping values if that is the case. For this comparison we don’t need to start from the bottom most leaf nodes (nodes with no children) as these nodes are considered to be correct heaps.

Since last node will be at position (n-1) for an array of length n so it’s parent node should be at index (n-1)/2 as per the equation. That is the index from where process of heapifying the array will start, in each iteration compare the parent node with left child and right child and swap the nodes if child is greater than the parent.

For example if we take the binary tree for the array {3 10 1 14 6 8}

Here last index is 5, which means last node is at that index. Thus the parent node should be at index (5-1)/2 = 2. From that index process starts.

heap sort program

In the next iteration for n=1, 10 is compared with its left and right children. Since (14 > 10) so a swap is required. Same way for n=0 again values will be swapped.

heapify method that is used for creating a heap structure (max heap) written in Java is as follows-

private void heapify(int[] numArr, int index, int i){
    // Getting parent and children indexes
    int rootIndex = i;
    int lc = 2*i + 1;
    int rc = 2*i + 2;
    
    //comparing left child value
    if(lc < index && numArr[lc] > numArr[rootIndex])
        rootIndex = lc;
    //comparing right child value
    if(rc < index && numArr[rc] > numArr[rootIndex])
        rootIndex = rc;
    // if change required then swap values and call method recursively
    if(rootIndex != i){
        swap(numArr, rootIndex, i);
        heapify(numArr, index, rootIndex);
    }
}

Steps for heap sort

Now when you know about heap data structure and how to create a heap from a given array it is easy to understand the heap sort.

In a max heap root element is always the greatest element of the array, that property of the heap is used in heap sort. Steps for heap sort are as follows-

  1. Heapify the array to get a heap structure.
  2. Swap the root element with the last element (Swap index 0 with index (n-1)).
  3. Heapify the array again without taking the last element as last element is already at its proper place. So array used now is from index 0 to index (array length -1). Once heap is created using this array largest element of this array will be the root of the heap. Repeat from step 2.

Heap sort Java program

public class HeapSort {

    public static void main(String[] args) {
        HeapSort hs = new HeapSort();
        int[] numArr = {3,10,1,14,6,8};
        //int[] numArr = {47, 85, 620, 3456, -7, 10, 4500, 106, -345, 1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
        //int[] numArr = {0, 21, 5, 1, 0, 2, 10, 15, 7, 5};
        hs.sort(numArr);
        System.out.println("Sorted array- " + Arrays.toString(numArr));
    }
    
    private void sort(int[] numArr){
        int arrLength = numArr.length;
        // create heap
        for(int i = (arrLength-1)/2; i >=0; i--){
            heapify(numArr, arrLength, i);
        }
        System.out.println("heapified array- " + Arrays.toString(numArr));
        // Sorting process
        // in the loop keep reducing the array that is used for creating heap
        for(int i = arrLength-1; i >= 0; i--){
            // Swap root and last nodes
            swap(numArr, i, 0);
            // build heap again
            heapify(numArr, i, 0);
        }
    }
    
    private void heapify(int[] numArr, int index, int i){
        // Getting parent and children indexes
        int rootIndex = i;
        int lc = 2*i + 1;
        int rc = 2*i + 2;
        //comparing left child value
        if(lc < index && numArr[lc] > numArr[rootIndex])
            rootIndex = lc;
        //comparing right child value
        if(rc < index && numArr[rc] > numArr[rootIndex])
            rootIndex = rc;
        // if change required then swap values and call method recursively
        if(rootIndex != i){
            swap(numArr, rootIndex, i);
            heapify(numArr, index, rootIndex);
        }
    }
    
    private void swap(int[] numArr, int index, int li){
        int temp = numArr[li];
        numArr[li] = numArr[index];
        numArr[index] = temp;
    }
}

Output

heapified array- [14, 10, 8, 3, 6, 1]
Sorted array- [1, 3, 6, 8, 10, 14]

Performance of heap sort

The height of a complete binary tree of n nodes is considered as log(n+1). In heap sort while building a heap comparison and swapping may be required at each level. Since heap building process is done for n/2 elements thus the time complexity of heap sort can be calculated as n/2*log(n+1). Thus in Big-O notation time complexity of heap sort is O(N*logN).

Heap sort may be slightly slower than quick sort in some scenarios but worst case scenario for quick sort is O(N2) where as for heap sort time complexity is O(N*logN) for best, average and worst case.

Since same array is used for building heap and for heap sorting so no auxiliary space is required making the space complexity of heap sort as O(1).

That's all for this topic Heap Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Quick Sort Program in Java
  2. Shell Sort Program in Java
  3. Find Duplicate Characters in a String With Repetition Count - Java Program
  4. How to Run a Shell Script From Java Program
  5. Producer-Consumer Java Program Using wait notify

You may also like-

  1. How to Count Lines in a File - Java Program
  2. Compressing And Decompressing File in GZIP Format - Java Program
  3. Converting Numbers to Words - Java Program
  4. Array Rotation Java Program
  5. How to Create Immutable Class in Java
  6. BigDecimal in Java
  7. Reflection in Java - Getting Class Information
  8. How HashMap Internally Works in Java