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.

Table of contents

Heap data structure
Types of heap
Heap data structure creation in program
Creating heap from tree
Steps for heap sort
Heap sort Java program
Performance of heap sort

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.

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 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}

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.

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-

Heapify the array to get a heap structure.
Swap the root element with the last element (Swap index 0 with index (n-1)).
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(N²) 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

You may also like-

Tech Tutorials

Tuesday, March 15, 2022