Heap sort algorithm is a comparison-based sorting technique based on a binary heap data structure. It’s similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.
Here’s a step-by-step explanation of the Heap Sort algorithm with an example along with the visualization tool.
Steps to Perform Heap Sort
- Build a Max-Heap from the input data.
- Swap the root of the heap (the largest element) with the last element of the heap.
- Reduce the size of the heap by one.
- Heapify the root element to ensure the heap property is maintained.
- Repeat steps 2 – 4 until the heap size is greater than 1.
Heap Sort Visualization Tool
Example Array
Let us consider an array: [4,10,3,5,1]
Step 1: Build a Max-Heap
- We start by converting the array into a binary tree and then adjust it to satisfy the max-heap property.
- Heapify the Sub-tree Rooted at Index 1</span
- Current node: (10)
- Children: (5) and (1)
- Since 10 is larger than both its children, no changes are needed.
- Heapify the Sub-tree Rooted at Index 0
- Current node: 4
- Children: (10) and (3)
- Since (10) is larger than (4), swap them.
- Now, heapify the sub-tree rooted at index 1 (where 4 was moved):
- Current node: (4)
- Children: (5) and (1)
- Since (5) is larger than (4), swap them. The max heap is now built.
- We repeatedly extract the maximum element from the heap (the root) and rebuild the heap with the remaining elements.
- Extract the Root (10) and Swap with the Last Element (1)
- Remove 10 (last element). Heap size is reduced by one. Now, heapify the root:
- Current node: (1)
- Children: (5) and (3)
- Swap (1) with (5).
- Heapify the sub-tree rooted at index 1 (where 1 was moved):
- Current node: (1)
- Children: (4)
- Swap (1) with (4)
- Remove 5 (last element). Heap size is reduced by one. Now, heapify the root:
- Current node: (1)
- Children: (4) and (3)
- Swap (1) with (4)
- Now no further heapify needed as 1 has no children.
- Extract the Root (4) and Swap with the Last Element (1)
- Remove 4 (last element). Heap size is reduced by one. Now, heapify the root:
- Current node: (1)
- Children: (3)
- Swap (1) with (3)
- No further heapify needed as (1) has no children.
- Extract the Root (3) and Swap with the Last Element (1)
Pseudocode of Heap Sort Algorithm
Main Function of Heap Sort
HEAPSORT(arr)
n = length(arr)
// Step 1: Build a max-heap
for i = n / 2 - 1 down to 0
HEAPIFY(arr, n, i)
// Step 2: Extract elements from heap
for i = n - 1 down to 0
// Move current root to end
swap arr[0] with arr[i]
// Call heapify on the reduced heap
HEAPIFY(arr, i, 0)
Heapify Function
HEAPIFY(arr, n, i)
largest = i // Initialize largest as root
left = 2 * i + 1 // left child index
right = 2 * i + 2 // right child index
// If left child is larger than root
if left < n and arr[left] > arr[largest]
largest = left
// If right child is larger than largest so far
if right < n and arr[right] > arr[largest]
largest = right
// If largest is not root
if largest != i
swap arr[i] with arr[largest]
// Recursively heapify the affected sub-tree
HEAPIFY(arr, n, largest)
Explanation of Pseudocode
- HEAPSORT Function:
- We start by building a max-heap from the input array. This is done by calling the HEAPIFY function for each non-leaf node, starting from the last non-leaf node up to the root.
- After building the max-heap, we repeatedly extract the maximum element (root of the heap) and move it to the end of the array. Then, we call the HEAPIFY function to restore the heap property for the reduced heap.
- HEAPIFY Function:
- This function ensures the max-heap property for a subtree rooted at the given index i. It compares the root with its left and right children and swaps the largest of the three with the root if necessary.
- If a swap is made, the HEAPIFY function is called recursively on the affected sub-tree to ensure the heap property is maintained.
Java Code for Heap Sort
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Step 1: Build a max-heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Step 2: Extract elements from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// 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 swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Utility function to print array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Main method
public static void main(String args[]) {
int arr[] = {4, 10, 3, 5, 1};
HeapSort heapSort = new HeapSort();
heapSort.sort(arr);
System.out.println("Sorted array is:");
printArray(arr);
}
}
Time Complexity
Heap Sort involves two main phases: building the heap and extracting elements from the heap.
- Building the Max-Heap:
- We start from the last non-leaf node and heapify each node.
- The time complexity for heapifying a single node is O(log n), where n is the number of elements in the heap.
- Since we are heapifying n/2 nodes, the total time complexity for building the heap is O(n).
- Extracting Elements from the Heap:
- We repeatedly remove the maximum element (the root of the heap) and heapify the reduced heap.
- Each extraction involves a heapify operation which takes O(log n) time.
- Since we perform n-1 extraction operations, the total time complexity for this phase is O(n log n).
Combining both phases, the overall time complexity of Heap Sort is: O(n) + O(n log n) = O(n log n)
Space Complexity
Heap Sort is an in-place sorting algorithm, meaning it requires a constant amount of additional space. The only extra space required is for a few temporary variables used during the swapping process.
Auxiliary Space: O(1)
Therefore, the space complexity of Heap Sort is O(1). Heap Sort is particularly advantageous when an in-place sort with a guaranteed O(n log n) time complexity is required. However, it is not a stable sort, meaning that equal elements may not retain their relative order. This can be a consideration when choosing a sorting algorithm for specific applications.
Related Articles
Frequently Asked Questions
All possible combinations of n objects are produced by Heap’s algorithm. In 1963, B. R. Heap made the initial proposal for it. The algorithm creates each permutation from the preceding one by switching a single pair of elements, hence minimizing movement.
Heap Sort is frequently used in operating systems to control memory allocation, as seen in the implementation of the free and malloc functions. An operating system’s heap segment is used to dynamically allocate and deallocate memory using these functions.
Although it can be done in O(n) complexity, searching is not best served by heaps. An array can be sorted using heap sort; however, to do so, an array of n integers must first be built, and only then can heap sort be used.
→ There are several advantages of Heap Sort Algorithm:
- Effective for huge datasets: Heap Sort works well for sorting large arrays, with an average and worst-case time complexity of O(n log n).
- Sorting in-place: It is effective in memory-constrained environments because it doesn’t require any more memory space than the original array.
- Not recursive: Heap Sort is iterative, unlike algorithms like Quicksort, it does not suffer from stack overflow for very large datasets.
- Priority Queues: When implementing priority queues, where the element with the highest priority is accessed first, the underlying heap structure can be utilized effectively.
5 thoughts on “Heap Sort Algorithm”