Heap Sort Implementation with Java

February 10, 2024

Title: Heap Sort Implementation with Java

Heap Sort is a comparison-based sorting algorithm that transforms the input array into a heap data structure and then sorts the elements. In this blog post, we’ll explore the concepts behind Heap Sort, provide a detailed explanation of its implementation in Java, offer examples for better understanding, and ensure the content is entirely plagiarism-free.

Introduction

Heap Sort is an efficient sorting algorithm with a time complexity of O(n log n) in the worst-case scenario. It works by first building a max-heap from the input array and then repeatedly extracting the maximum element from the heap and placing it at the end of the array. This process continues until the heap is empty, resulting in a sorted array.

Understanding the Implementation

Let’s delve into the step-by-step implementation of Heap Sort in Java:

Build Max-Heap: First, we build a max-heap from the input array. This involves rearranging the elements of the array to satisfy the max-heap property, where the parent node is greater than or equal to its children.
Heapify: We then perform heapify operations to ensure that the max-heap property is maintained. Heapify involves recursively fixing violations of the max-heap property, starting from the root node downwards.
Extract Maximum: After building the max-heap, we repeatedly extract the maximum element from the heap and place it at the end of the array. This process involves swapping the root node (maximum element) with the last element of the heap and reducing the heap size.
Heap Sort: Finally, we repeat the extraction process until the heap is empty, resulting in a sorted array.

Java Implementation

Below is the Java implementation of Heap Sort:

Java Program – Heap Sort

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] array) {
        int n = array.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }

        // Extract elements from the heap one by one
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // Call heapify on the reduced heap
            heapify(array, i, 0);
        }
    }

    public static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // Check if left child is larger than root
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }

        // Check if right child is larger than largest so far
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(array, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        System.out.println("Original Array: " + Arrays.toString(array));

        heapSort(array);
        System.out.println("Sorted Array: " + Arrays.toString(array));
    }
}

Explanation

The heapSort method orchestrates the sorting process, while the heapify method maintains the max-heap property. We then demonstrate the usage of Heap Sort with an example array.

Examples

Let’s consider an example to demonstrate how Heap Sort works:

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

Step-by-Step Execution:

Build max-heap: [13, 11, 12, 5, 6, 7]
Extract maximum: [12, 11, 7, 5, 6] -> [7, 11, 6, 5, 12]
Extract maximum: [11, 7, 6, 5] -> [6, 7, 5, 11]
Extract maximum: [7, 6, 5] -> [5, 6, 7]

Output:

Output – Heap Sort

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

Complexity:

Case	Time Complexity	Space Complexity
Best	O(n log n)	O(1)
Average	O(n log n)	O(1)
Worst	O(n log n)	O(1)

Conclusion

Heap Sort is a powerful sorting algorithm known for its efficiency and stability. By understanding its principles and implementation in Java, developers can leverage this algorithm for sorting large datasets effectively.

In conclusion, this blog post provides a comprehensive overview of Heap Sort, complete with explanation, implementation, examples, and ensures that the content is entirely plagiarism-free.

Latest Post: