Heap Sort
Heap sort uses a binary heap to sort an array. First, it builds a max-heap from the array, then repeatedly extracts the maximum and places it at the end. Time O(n log n), in-place, not stable.
Java implementation:
public static void heapSort(int[] arr) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
// Extract elements one by one
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
private 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, largest);
heapify(arr, n, largest);
}
}
Two Minute Drill
- Heap sort uses a max-heap; O(n log n) time.
- In-place, not stable.
- Excellent for large data and guaranteed O(n log n).
- Often used when stability is not required.
Need more clarification?
Drop us an email at career@quipoinfotech.com