Java Heap Sort Tutorial 📝

Welcome to the Java Heap Sort tutorial! In this comprehensive guide, we'll learn about the Heap Sort algorithm and implement it in Java. Let's dive right in!

What is Heap Sort? 🎯

Heap Sort is a sorting algorithm that belongs to the comparison sort family. It works on the principle of building a binary heap and then sorting the elements by swapping the root with the last element and then rebuilding the heap.

Why Heap Sort? 💡

Efficient: Heap Sort has a worst-case time complexity of O(n log n), making it faster than other sorts for large datasets.
In-place: Unlike QuickSort, Heap Sort does not require additional space for the stack.
Easy to implement: Heap Sort is relatively simple to implement compared to other sorting algorithms like Merge Sort or Quick Sort.

The Heap Data Structure 📝

A heap is a complete binary tree that either maximizes or minimizes the key at each node. In Heap Sort, we'll be using a Max Heap, where the parent nodes are always greater than or equal to their child nodes.

Heap Sort Algorithm 🎯

Build Max Heap: Convert the given array into a Max Heap.
Swap root with the last element: Swap the root element with the last element.
Re-heapify: Re-heapify the array from the new root, which is now the last element.
Repeat steps 2 and 3 until the array is sorted.

Implementing Heap Sort in Java 💡

Let's write a Heap Sort implementation in Java:

java

public class HeapSort {
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest]) {
            largest = l;
        }
        if (r < n && arr[r] > arr[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    private static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Unsorted array:");
        printArray(arr);

        heapSort(arr);
        System.out.println("\nSorted array:");
        printArray(arr);
    }

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

Quiz Time! 🎯

That's it for our Heap Sort tutorial! We hope you enjoyed learning about this efficient sorting algorithm and can now implement it in your own projects. Happy coding! 🚀