What is Heap Sort?
Heap Sort is a popular and efficient sorting algorithm that is based on the Binary Heap data structure. It works by visualizing the elements of the array as a special kind of complete binary tree called a heap.
The algorithm operates in two main phases: building a max-heap from the unsorted array, and then repeatedly extracting the maximum element from the heap and rebuilding it until the array is sorted.
Visual Example
A Max-Heap where the root is always the largest element. We swap it with the last element and remove it to sort the array.
Algorithm Strategy
1. Build Max Heap
Rearrange the array elements so they form a Max-Heap (where the parent node is greater than its children).
2. Swap Root
The largest item is stored at the root of the heap. Swap it with the last item of the heap followed by reducing the size of heap by 1.
3. Heapify and Repeat
Heapify the root of the tree to maintain the max-heap property. Repeat this process while size of heap is greater than 1.
Complexity Analysis
Time complexity is O(N log N) for all cases (best, average, worst) because building a heap takes O(N) and then we call heapify N times which takes O(log N) each time.
Time Complexity: O(N log N)
Key Takeaways
- Heap Sort is an in-place algorithm, meaning it takes O(1) auxiliary space.
- Unlike Quick Sort, its worst-case time complexity is O(N log N).
- It is not a stable sort, meaning it does not preserve the relative order of elements with equal keys.