Heap Sort Example in Java

Introduction

Heap Sort is a classic Java console program that demonstrates the concept with complete source code and sample output. These programs cover your first Java class, constructors, methods and simple OOP building blocks.

This tutorial walks through the program line by line, explains how the logic works, and highlights best practices you can apply in your own code.

Definition

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Heap Sort Example Program

import java.util.Scanner;

public class HeapSort{    
	private static int N;
    public static void sort(int arr[]){       
		heapMethod(arr);        
        for (int i = N; i > 0; i--){
            swap(arr,0, i);
            N = N-1;
            heap(arr, 0);
        }
    }     
    public static void heapMethod(int arr[]){
        N = arr.length-1;
        for (int i = N/2; i >= 0; i--)
            heap(arr, i);        
    }
    public static void heap(int arr[], int i){ 
        int left = 2*i ;
        int right = 2*i + 1;
        int max = i;
        if (left <= N && arr[left] > arr[i])
            max = left;
		if (right <= N && arr[right] > arr[max])        
            max = right;
        if (max != i){
            swap(arr, i, max);
            heap(arr, max);
        }
    }    
    public static void swap(int arr[], int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp; 
    }    
    public static void main(String[] args) {
        Scanner in = new Scanner( System.in );        
        int n;    
        System.out.println("Enter the number of elements to be sorted:");
        n = in.nextInt();    
        int arr[] = new int[ n ];
        System.out.println("Enter "+ n +" integer elements");
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        sort(arr);
        System.out.println("After sorting ");        
        for (int i = 0; i < n; i++)
            System.out.println(arr[i]+" ");            
        System.out.println();            
    }    
}

Sample Output

Enter the number of elements to be sorted:
6
Enter 6 integer elements
99
54
67
32
1
78
After sorting
1
32
54
67
78
99

When to use

Use this heap sort example when learning or revising core Java syntax.

How it works

1. Execution begins in the main method — the JVM calls this method when you run the class.

2. import java.util.Scanner; imports a class used later in the program.

3. for (int i = N; i > 0; i--){ updates a variable used in the calculation or output.

4. N = N-1; updates a variable used in the calculation or output.

5. N = arr.length-1; updates a variable used in the calculation or output.

6. for (int i = N/2; i >= 0; i--) updates a variable used in the calculation or output.

7. int left = 2*i ; updates a variable used in the calculation or output.

8. The if statement runs the nested code only when the condition is true.

Best Practices

• Name classes in PascalCase and follow one public class per file when starting out.
• Keep main short — delegate work to other methods as programs grow.

Common Mistakes

• Copying code without understanding each line — practice by changing one statement at a time.
• Mismatching the public class name and the .java filename.
• Forgetting semicolons at the end of statements.