Heap Sort in Java

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It is an efficient algorithm with a worst-case time complexity of O(n log⁡ n).

How Does Heap Sort Work?

Heap Sort works by leveraging the properties of a binary heap to sort an array. Here’s how it works step by step:

Step-by-Step Explanation:

  1. Build a Max-Heap:
    • The first step is to transform the input array into a max-heap, where each parent node is greater than or equal to its child nodes.

    • This ensures that the largest element in the array is at the root of the heap (index 0).

Example:
Input Array: [12, 11, 13, 5, 6, 7]
Max-Heap: [13, 11, 12, 5, 6, 7]

  1. Extract the Maximum Element:
    • Swap the root of the heap (largest element) with the last element of the heap.

    • Reduce the size of the heap by one (exclude the last element, as it is now sorted).

    • Restore the max-heap property by calling the heapify function on the root.
    Example:
    Swap [13] with [7]: [7, 11, 12, 5, 6, 13]
    Heapify: [12, 11, 7, 5, 6, 13]
  1. Repeat the Process:
    • Continue swapping the root with the last unsorted element and heapifying the root until the heap size is 1.
    Example:
    • Swap [12] with [6]: [6, 11, 7, 5, 12, 13]
    • Heapify: [11, 6, 7, 5, 12, 13]
    • Swap [11] with [5]: [5, 6, 7, 11, 12, 13]
    • Heapify: [7, 6, 5, 11, 12, 13]
  1. Sorted Array:
    • Once all elements are extracted, the array is sorted in ascending order.
    Final Sorted Array: [5, 6, 7, 11, 12, 13]

How Heapify Works?

The heapify function ensures that the max-heap property is maintained after each extraction. Here’s how it works:

  1. Compare the parent node with its left and right child nodes.
  2. If a child node is larger than the parent, swap the parent with the largest child.
  3. Recursively apply the heapify process to the affected subtree.

Example:
Input Heap: [7, 11, 6, 5, 12, 13]
Heapify at Root (7):

  • Compare 7, 11, and 6.
  • Swap 7 with 11: [11, 7, 6, 5, 12, 13].

Visual Example:

Initial Array: [12, 11, 13, 5, 6, 7]

  1. Build Max-Heap: [13, 11, 12, 5, 6, 7]
  2. Extract Max (13): [7, 11, 12, 5, 6, 13] → Heapify → [12, 11, 7, 5, 6, 13]
  3. Extract Max (12): [6, 11, 7, 5, 12, 13] → Heapify → [11, 6, 7, 5, 12, 13]
  4. Extract Max (11): [5, 6, 7, 11, 12, 13] → Heapify → [7, 6, 5, 11, 12, 13]
  5. Extract Max (7): [5, 6, 7, 11, 12, 13]
  6. Extract Max (6): [5, 6, 7, 11, 12, 13]

Sorted Array: [5, 6, 7, 11, 12, 13]

Heap Sort Program in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.javacodepoint.sort;
 
public class HeapSort {
     
    // Function to sort an array using Heap Sort
    public static void heapSort(int[] array) {
        int n = array.length;
 
        // Step 1: Build Max-Heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
 
        // Step 2: Extract elements from the heap one by one
        for (int i = n - 1; i > 0; i--) {
            // Move the current root (max) to the end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
 
            // Restore the heap property for the reduced heap
            heapify(array, i, 0);
        }
    }
 
    // Function to maintain the heap property
    public static void heapify(int[] array, int heapSize, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child index
        int right = 2 * i + 2; // Right child index
 
        // If left child is larger than root
        if (left < heapSize && array[left] > array[largest]) {
            largest = left;
        }
 
        // If right child is larger than largest so far
        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }
 
        // If largest is not the root
        if (largest != i) {
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
 
            // Recursively heapify the affected subtree
            heapify(array, heapSize, largest);
        }
    }
 
    public static void main(String[] args) {
        int[] numbers = { 12, 11, 13, 5, 6, 7 };
 
        System.out.println("Original Array:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
 
        // Sort the array using Heap Sort
        heapSort(numbers);
 
        System.out.println("\nSorted Array:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

OUTPUT:

Time Complexity:

  1. Build Max-Heap: O(n)
  2. Heapify: O(log⁡ n)
  3. Extract Elements: O(n log⁡ n)

Overall: O(n log⁡ n) in all cases (best, average, worst).

Space Complexity:

  • O(1): In-place sorting algorithm.

Also Read: Selection Sort | Insertion Sort | Bubble Sort | Merge Sort

Java logical programs list


Java Basic Programs

Java String Programs

Java String Array Programs

Java Miscellaneous Programs

Java Programs based on the Collection Framework

Leave a Reply

Your email address will not be published. Required fields are marked *