HeapProblem 2 of 18
Sort an Array using heap (HeapSort)
Problem Statement
Sort an array using Heap Sort algorithm. Heap Sort uses the heap data structure to efficiently sort elements in-place.
Example:
- Input:
arr = [12, 11, 13, 5, 6, 7] - Output:
[5, 6, 7, 11, 12, 13] - Explanation: The array is sorted in ascending order using heap sort.
Approach 1: Using Extra Space (Brute Force)
Intuition
Build a min-heap from the array elements, then extract minimum elements one by one to get the sorted array. This uses extra space for the heap.
Algorithm
- Insert all elements into a min-heap
- Extract minimum element repeatedly
- Store extracted elements in result array
java
import java.util.PriorityQueue;
public class Solution {
public int[] heapSortExtraSpace(int[] arr) {
// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Insert all elements
for (int num : arr) {
minHeap.offer(num);
}
// Extract elements in sorted order
int[] result = new int[arr.length];
int i = 0;
while (!minHeap.isEmpty()) {
result[i++] = minHeap.poll();
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Building heap takes O(n), n extractions take O(n log n)
- Space Complexity: O(n) - Extra space for heap and result array
Approach 2: In-Place Heap Sort (Optimal)
Intuition
Build a max-heap in-place within the array. Then repeatedly swap the root (maximum) with the last unsorted element and heapify. This sorts in ascending order without extra space.
Algorithm
- Build max-heap from array using bottom-up heapify - O(n)
- Swap root (max element) with last element
- Reduce heap size by 1
- Heapify the root to restore max-heap property
- Repeat steps 2-4 until heap size becomes 1
java
public class HeapSort {
private void heapify(int[] arr, 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 && arr[left] > arr[largest]) {
largest = left;
}
// Check if right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
public void sort(int[] arr) {
int n = arr.length;
// Build max-heap (bottom-up)
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--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
HeapSort hs = new HeapSort();
int[] arr = {12, 11, 13, 5, 6, 7};
hs.sort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}Complexity Analysis
- Time Complexity: O(n log n)
- Building heap: O(n)
- n-1 extractions with heapify: O(n log n)
- Space Complexity: O(1) - In-place sorting (O(log n) for recursion stack)
Approach 3: Iterative Heapify (Space Optimized)
Intuition
Convert recursive heapify to iterative to eliminate recursion stack space.
Algorithm
Same as optimal but with iterative heapify implementation.
java
public class HeapSortIterative {
private void heapifyIterative(int[] arr, int n, int i) {
while (true) {
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) {
break;
}
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
i = largest;
}
}
public void sort(int[] arr) {
int n = arr.length;
// Build max-heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyIterative(arr, n, i);
}
// Extract elements
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapifyIterative(arr, i, 0);
}
}
}Complexity Analysis
- Time Complexity: O(n log n)
- Space Complexity: O(1) - True constant space (no recursion stack)
Key Takeaways
- Heap Sort guarantees O(n log n) time in all cases (best, average, worst)
- In-place sorting makes it space efficient with O(1) auxiliary space
- Not stable - relative order of equal elements may change
- Max-heap for ascending order, min-heap for descending order
- Build heap takes O(n), not O(n log n) due to height distribution
- Useful when guaranteed O(n log n) is needed without extra space
- Worse cache performance than quicksort due to non-sequential access