Java Program to Sort Array Elements using Heap Sort

This is the Java Program to Implement Heap Sort on an Array of n Elements.

Problem Description

Given an array of integers, sort the array using heap sort algorithm.

Problem Solution

The idea is to create a max heap of the array elements. Then, obtain the maximum element from the heap, interchange it with the last element and finally heapify the remaining (n-1) elements. Repeat this procedure until zero elements are left.

Program/Source Code

Here is the source code of the Java Program to Implement Heap Sort on an Array of n Elements. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

```
 
```

//Java Program to Implement Heap Sort on an Array of n Elements

```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
import java.util.Arrays;
```
```
 
```
```
public class HeapSort {
```

    //Function to sort the array using heapsort

```
    static void heapSort(int[] array){
```
```
             buildHeap(array);
```

             int i,temp = array.length-1;

             for(i = array.length-1; i>=1; i--){

```
                 int x = array[0];
```

                 array[0] = array[temp];

```
                 array[temp] = x;
```
```
                 temp--;
```

                 heapifyDownwards(array,0,temp);

```
             }
```
```
    }
```
```
    // Function to heapify the array
```

    static void heapifyDownwards(int[] array,int i,int n){

```
        if(i>n)
```
```
        {
```
```
            return;
```
```
        }
```
```
        int left,right,index = i;
```
```
        left = 2*i;
```
```
        right= 2*i+1;
```
```
        boolean change = false;
```

        if(left<=n && array[i]<array[left]){

```
            index = left;
```
```
            change = true;
```
```
        }
```

        if(right<=n && array[right]>array[index]){

```
            index = right;
```
```
            change = true;
```
```
        }
```
```
        if(!change)
```
```
        {
```
```
            return;
```
```
        }
```
```
        int temp = array[index];
```
```
        array[index] = array[i];
```
```
        array[i] = temp;
```

        heapifyDownwards(array,index,n);

```
    }
```
```
    // Function to build a max-heap
```
```
    static void buildHeap(int[] array){
```
```
        int i = array.length/2-1;
```
```
        for(;i>=0;i--){
```

            heapifyDownwards(array,i,array.length-1);

```
        }
```
```
    }
```

    // Function to read input and display the output

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int size;
```

        System.out.println("Enter the size of the array");

```
        try {
```

            size = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] array = new int[size];
```

        System.out.println("Enter array elements");

```
        int i;
```

        for (i = 0; i < array.length; i++) {

```
            try {
```

                array[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error Occurred");

```
            }
```
```
        }
```

        System.out.println("The initial array is");

        System.out.println(Arrays.toString(array));

```
        heapSort(array);
```

        System.out.println("The sorted array is");

        System.out.println(Arrays.toString(array));

```
    }
```
```
}
```

Program Explanation

1. The function buildHeap() is used to build a max-heap from the array elements. It starts from the internal nodes of the heaps and heapifies them downwards.
2. In function heapifyDownwards(), the element at index i, is compared with its children. If any child is greater than the parent, the nodes are swapped and the function is called recursively on the children.
3. In function heapSort(), firstly the buildHeap function is called.
4. The loop for(i = array.length-1; i>=1; i–), iterates through the heap swaps the first element with the last and heapifies the first element.

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
The initial array is
[9, 8, 7, 6, 5]
The sorted array is
[5, 6, 7, 8, 9]
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
8
7
6
9
9
6
7
8
The initial array is
[8, 7, 6, 9, 9, 6, 7, 8]
The sorted array is
[6, 6, 7, 7, 8, 8, 9, 9]

Sanfoundry Global Education & Learning Series – Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

« Prev - Java Program to Sort Names in an Alphabetical Order

Related Posts:

Recommended Articles: