Heap Sort
Heap Sort is a comparison-based sorting algorithm that uses a Binary Heap data structure. It first converts the given array into a Max Heap and then repeatedly removes the largest element from the heap and places it at the end of the array. This process continues until all elements are sorted.
Heap Sort is efficient because its time complexity remains O(n log n) in the best, average and worst cases. Unlike Merge Sort, Heap Sort performs sorting within the same array and requires very little additional memory.
Prerequisite
| Concept | Description |
|---|---|
| Arrays | Heap Sort is generally implemented using arrays. |
| Binary Tree | A Binary Heap is represented as a Complete Binary Tree. |
| Heap Property | Every parent node must be greater than or equal to its child nodes in a Max Heap. |
What is a Heap?
A Heap is a special type of complete binary tree that satisfies the Heap Property. There are two types of heaps:
- Max Heap: The parent node is always greater than or equal to its children.
- Min Heap: The parent node is always smaller than or equal to its children.
Heap Sort uses a Max Heap to arrange elements in ascending order.
Working Principle
Heap Sort performs sorting in two phases:
- Construct a Max Heap from the given array.
- Swap the root element with the last element, reduce the heap size, and restore the Max Heap property.
Illustration of Heap Sort
Example
Consider the following unsorted array.
20 50 30 10 60
Step 1 : Convert the array into a Max Heap.
Step 2 : Swap the root element (largest value) with the last element.
Step 3 : Reduce the heap size by one and restore the Max Heap property.
Step 4 : Repeat the process until the heap becomes empty and the array is completely sorted.
Heap Sort Algorithm
HeapSort(Array)
Step 1 : Build a Max Heap.
Step 2 : Swap the root element with the last element.
Step 3 : Reduce the heap size by one.
Step 4 : Restore the Max Heap property (Heapify).
Step 5 : Repeat Steps 2 to 4 until the heap contains only one element.
Step 6 : The array is now sorted.
Complexity Analysis
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n log n) | Building the heap and repeatedly restoring the heap property require logarithmic time. |
| Average Case | O(n log n) | The heap is rebuilt after every extraction of the largest element. |
| Worst Case | O(n log n) | Heap Sort maintains the same performance regardless of the input order. |
| Space Complexity | O(1) | Heap Sort is an in-place sorting algorithm and requires only a constant amount of extra memory. |
Advantages of Heap Sort
- Provides O(n log n) time complexity in all cases.
- Does not require additional memory for sorting.
- Suitable for large datasets.
- Performance is independent of the initial arrangement of data.
- Efficient for priority-based applications.
Limitations of Heap Sort
- Heap Sort is not a stable sorting algorithm.
- Implementation is more complex than Bubble Sort or Selection Sort.
- In practice, Quick Sort is often faster for in-memory sorting.
- Not suitable when preserving the order of equal elements is required.
Applications of Heap Sort
| Application | Description |
|---|---|
| Priority Queues | Efficient implementation of priority queue operations. |
| Operating Systems | Used in process scheduling and resource management. |
| Graph Algorithms | Used in algorithms such as Dijkstra's and Prim's. |
| Large Data Processing | Sorting large collections of data efficiently. |
| Embedded Systems | Useful where constant extra memory is preferred. |
Comparison of Heap Sort and Quick Sort
| Heap Sort | Quick Sort |
|---|---|
| Uses a Binary Heap. | Uses Pivot Partitioning. |
| Worst Case: O(n log n) | Worst Case: O(n²) |
| In-place sorting algorithm. | Mostly in-place sorting algorithm. |
| Not Stable. | Not Stable. |
| Performance is predictable. | Performance depends on Pivot selection. |