Table of Contents 📚
- Introduction to Heap Sort
- Understanding the Heap Data Structure
- Java Implementation
- Time and Space Complexity
- Summary
Introduction to Heap Sort 📜
Heap Sort is an efficient sorting algorithm that takes advantage of the properties of a binary heap data structure. It uses the heap to organize elements so that the maximum (or minimum) element can be removed efficiently, thereby sorting the array.
Understanding the Heap Data Structure 🌳
Before diving into the Heap Sort algorithm, let’s quickly understand what a heap is. A heap is a complete binary tree where each parent node is greater (in a max-heap) or smaller (in a min-heap) than or equal to its children. Heaps are commonly used to implement priority queues.
Implementation of Heap Sort in Java 🛠️
Below is a complete Java code that demonstrates the Heap Sort algorithm. We’ll use a max-heap to sort the array in ascending order.
public class HeapSort {
// Heapify subtree rooted at index i
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
// Swap arr[i] and arr[largest]
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Heapify the affected subtree
heapify(arr, n, largest);
}
}
// Heap Sort Function
public static void heapSort(int[] arr) {
int n = arr.length;
// Build a max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements one by one from heap and
// place it at the end, reducing heap size
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}Time and Space Complexity of Heap Sort ⏰📦
Time Complexity:
- Worst-case: O(nlogn)
- Average-case: O(nlogn)
- Best-case: O(nlogn)
Space Complexity:
- O(1) additional space (in-place sort)
Summary 📝
Heap Sort is an efficient sorting algorithm that works well for both small and large data sets. It takes advantage of the heap data structure to sort an array in O(nlogn) time complexity, making it a good choice for various applications.
If you find this guide useful, please share with others, and spread the knowledge!