Heap Sort Java Algorithm | JavaSorting

Total Views : 69
Zoom In Zoom Out Read Later Print

we will discuss two different ways to implement heap sorting In Java Application. The project download URL has been added so that you can easily execute the given program, with appropriate examples and samples outputs added for heap sort In Java.

Here we are using two ways for sorting but they are not different from each other. Only difference is how we get input from the user and store it. Sorting of the element will be done in same way.

We will use following 2 ways to implement heap Sort in Java.

1. Using Buffered Reader.
2. Using Array.

Heap Sort Using Buffered Reader

SortBufferReader.java

package com.manjeet.prodevsblog.heap;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SortBufferReader {

    public static void main(String[] args) throws IOException {

        System.out.println("Sorting Using Buffered Reader....");

        int n, i;
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter Number of Elements (n):");
        n = Integer.parseInt(b.readLine());
        int[] array = new int[n];

        System.out.println("Enter "+n+" Elements (Press Enter After Each Element) ");

        for( i = 0; i < n; i++) {
            array[i] = Integer.parseInt(b.readLine());
        }

        System.out.println( "Elements in Array Before Sorting...");
        printArray(array);

        sortArray(array);

        System.out.println( "Elements in Array After Sorting");
        printArray(array);
    }

    public static void sortArray(int[] array) {
        int temp, i;

        bHeap(array);

        for( i=(array.length)-1; i > 0;) {
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            sHeap(array, 0, i--) ;

        }
    }

    public static void bHeap(int[] array) {

        for(int i = (array.length/2) - 1; i >= 0; i--) {
            sHeap(array, i, array.length);
        }
    }

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

        int l = 2*i+1;
        int r = 2*i+2;

        int temp, largest;

        if(l < n && array[l] >array[i])
            largest = l;
        else
            largest = i;

        if(r < n && array[r] > array[largest])
            largest=r;

        if(largest != i) {
            temp = array[largest];
            array[largest] = array[i];
            array[i] = temp;

            sHeap(array, largest, n);
        }
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Output:

Sorting Using Buffered Reader....
Enter Number of Elements (n):6
Enter 6 Elements (Press Enter After Each Element) 
34
76
123
678
12
4
Elements in Array Before Sorting...
34 76 123 678 12 4 
Elements in Array After Sorting
4 12 34 76 123 678 

Process finished with exit code 0

Heap Sort Using Array & Scanner

SortArray.java

package com.manjeet.prodevsblog.heap;

import java.util.Scanner;

public class SortArray {

    public static void main(String[] args) {
        
        System.out.println("Sorting Using Array & Scanner....");

        int n, i;
        Scanner s = new Scanner(System.in);

        System.out.print("Enter Number of Elements (n):");
        n = s.nextInt();
        int[] array = new int[n];

        System.out.println("Enter "+n+" Elements (Press Enter After Each Element) ");

        for( i = 0; i < n; i++) {
            array[i] = s.nextInt();
        }

        System.out.println( "Elements in Array Before Sorting...");
        printArray(array);

        sortArray(array);

        System.out.println( "Elements in Array After Sorting");
        printArray(array);
    }

    public static void sortArray(int[] array) {
        int temp, i;

        bHeap(array);

        for( i=(array.length)-1; i > 0;) {
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            sHeap(array, 0, i--) ;

        }
    }

    public static void bHeap(int[] array) {

        for(int i = (array.length/2) - 1; i >= 0; i--) {
            sHeap(array, i, array.length);
        }
    }

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

        int l = 2*i+1;
        int r = 2*i+2;

        int temp, largest;

        if(l < n && array[l] >array[i])
            largest = l;
        else
            largest = i;

        if(r < n && array[r] > array[largest])
            largest=r;

        if(largest != i) {
            temp = array[largest];
            array[largest] = array[i];
            array[i] = temp;

            sHeap(array, largest, n);
        }
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + ", ");
        }
        System.out.println();
    }
}

Output:

Sorting Using Array & Scanner....
Enter Number of Elements (n):6
Enter 6 Elements (Press Enter After Each Element) 
9
7
3
62
4
19
Elements in Array Before Sorting...
9, 7, 3, 62, 4, 19, 
Array Loop 5 in sortArray() Start ----------------
19, 9, 3, 7, 4, 62, 
Array Loop 4 in sortArray() End ----------------
Array Loop 4 in sortArray() Start ----------------
9, 7, 3, 4, 19, 62, 
Array Loop 3 in sortArray() End ----------------
Array Loop 3 in sortArray() Start ----------------
7, 4, 3, 9, 19, 62, 
Array Loop 2 in sortArray() End ----------------
Array Loop 2 in sortArray() Start ----------------
4, 3, 7, 9, 19, 62, 
Array Loop 1 in sortArray() End ----------------
Array Loop 1 in sortArray() Start ----------------
3, 4, 7, 9, 19, 62, 
Array Loop 0 in sortArray() End ----------------
Elements in Array After Sorting
3, 4, 7, 9, 19, 62, 

Process finished with exit code 0

Sample Recursive Calls and Loop Outputs :

Elements in Array Before Sorting...
9, 7, 3, 62, 4, 19, 
sHeap :- 9, 7, 3, 62, 4, 19, 
sHeap :- 9, 7, 19, 62, 4, 3, 
bHeap :- 9, 7, 19, 62, 4, 3, 
sHeap :- 9, 7, 19, 62, 4, 3, 
sHeap :- 9, 62, 19, 7, 4, 3, 
bHeap :- 9, 62, 19, 7, 4, 3, 
sHeap :- 9, 62, 19, 7, 4, 3, 
sHeap :- 62, 9, 19, 7, 4, 3, 
bHeap :- 62, 9, 19, 7, 4, 3, 
Array Loop 5 in sortArray() Start ----------------
sHeap :- 3, 9, 19, 7, 4, 62, 
sHeap :- 19, 9, 3, 7, 4, 62, 
19, 9, 3, 7, 4, 62, 
Array Loop 5 in sortArray() End ----------------
Array Loop 4 in sortArray() Start ----------------
sHeap :- 4, 9, 3, 7, 19, 62, 
sHeap :- 9, 4, 3, 7, 19, 62, 
sHeap :- 9, 7, 3, 4, 19, 62, 
9, 7, 3, 4, 19, 62, 
Array Loop 4 in sortArray() End ----------------
Array Loop 3 in sortArray() Start ----------------
sHeap :- 4, 7, 3, 9, 19, 62, 
sHeap :- 7, 4, 3, 9, 19, 62, 
7, 4, 3, 9, 19, 62, 
Array Loop 3 in sortArray() End ----------------
Array Loop 2 in sortArray() Start ----------------
sHeap :- 3, 4, 7, 9, 19, 62, 
sHeap :- 4, 3, 7, 9, 19, 62, 
4, 3, 7, 9, 19, 62, 
Array Loop 2 in sortArray() End ----------------
Array Loop 1 in sortArray() Start ----------------
sHeap :- 3, 4, 7, 9, 19, 62, 
3, 4, 7, 9, 19, 62, 
Array Loop 1 in sortArray() End ----------------
Elements in Array After Sorting
3, 4, 7, 9, 19, 62, 

1. The numbers entered by the user will be stored in the Array array[].

2. The function printArray() prints the array elements, function sortArray() will sort the array elements using heap sort.

3. In the heap tree every parent node should not contain greater child node, so we need to build the complete ordered tree using bHeap() method.

4. First, we have to order the right-most tree, then the left-most tree.

5. The array elements are 9, 7, 3, 62, 4, 19, represents a not ordered tree.

6. At height 7, 3 has the greater child 19 so move 3 to downward and place 19 in the position of 3. The left-most tree 7 has the greater child 62 so move 7 to downward and place 62 in the position of 7.

7. Now the array is 9, 62, 19, 7, 4, 3. The 62 is the greater child of 9 in the left-most tree. So move 9 to downward and place 62 at the position of 9. Now the series is 62, 9, 19, 7, 4, 3.

8. Now sort the elements of the tree using sort() method.

9. First, delete the top element of the tree and place that element at last node of the tree. After delete and place the top element, again build a complete ordered tree with remaining elements. Repeat this until the array is sorted completely.

10. From the complete ordered array elements delete 62 and place it at last index of the array, build the complete ordered tree.

11. Now the array is 19, 9, 3, 7, 4, 62. Next, delete 19 and place it at the proper position of the array and build the complete ordered tree. Now the array is 9,4,3,7,19,62.

12. Delete 9 and build complete ordered tree, the array is 4,7,3,9,19,62. Delete 4 and build the complete ordered tree, now the array is 7,3,4,9,19,62. Delete 7 and build the complete ordered tree. Now the sorted array is 3, 7, 4, 9, 19, 62.

You can download the Complete project from below link.

See More

Latest Photos