Heap Sort
Problem
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region.
Examples:
Example 1:
Input: arr = [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]
Explanation: The algorithm builds a max heap and then repeatedly extracts the maximum element to sort the array.
Example 2:
Input: arr = [4, 10, 3, 5, 1]
Output: [1, 3, 4, 5, 10]
Explanation: The algorithm efficiently sorts the array using the heap data structure.
Solution
Intuition
- Heap Sort uses a binary heap data structure, which is a complete binary tree where each node is greater than or equal to its children (max heap).
- The algorithm first builds a max heap from the input array.
- Then, it repeatedly extracts the maximum element (root of the heap) and places it at the end of the array.
- After each extraction, it maintains the heap property by heapifying the reduced heap.
Approach
- Build a max heap from the input array.
- Extract the maximum element (root) and place it at the end of the array.
- Reduce the heap size by 1 and heapify the root element to maintain the max heap property.
- Repeat steps 2 and 3 until the heap size is 1.
Complexity Analysis
- Time Complexity: O(n log n) for all cases (best, average, and worst) because building a heap takes O(n) time and each of the n heapify operations takes O(log n) time.
- Space Complexity: O(1) as it sorts in-place, requiring only a constant amount of additional memory.
Implementation
CPP
Run your code to see output here