heap sort Algorithm
Heap Sort Algorithm is a highly efficient comparison-based sorting technique that employs a binary heap data structure to order the elements in a given array or list. It is an in-place and non-stable sorting algorithm, which works on the principles of divide and conquer strategy, and is particularly suitable for sorting large datasets. The central idea of the Heap Sort Algorithm is to build a binary heap, which is a special kind of binary tree, having two properties: shape property and heap property. In the shape property, the binary tree is either a complete binary tree or almost complete binary tree, and in the heap property, the parent nodes are either greater than (for max-heap) or smaller than (for min-heap) the child nodes.
The Heap Sort Algorithm comprises two main subroutines: building the initial max-heap from the given input elements, and extracting the maximum element from the max-heap and inserting it into the sorted array in a step-by-step manner. The process starts by constructing a max-heap from the given elements, which can be accomplished by iterating through the elements and performing a 'heapify' operation to maintain the heap property. Once the max-heap is formed, the largest element resides at the root of the heap. The algorithm then swaps this largest element with the last element of the heap, effectively shrinking the heap size by one and placing the largest element in its correct sorted position. The 'heapify' operation is performed again to restore the max-heap property, and the process continues until the entire array is sorted. The time complexity of the Heap Sort Algorithm is O(n log n) for the best, average, and worst cases, making it an ideal choice for sorting large datasets with minimal overhead.
package Misc;
public class heap_sort {
public void sort(int[] arr) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
/* A utility function to print array of size n */
static void printArray(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
heap_sort ob = new heap_sort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
