Heap sort is a comparison-based sorting algorithm that efficiently sorts elements in an array or other data structures. It is known for its simplicity, stability, and consistent performance. This article will provide a comprehensive overview of heap sort in C program, explaining its key concepts and implementation steps and analysing its time and space complexities.
Heap sort in C is an efficient sorting algorithm that uses a binary tree structure called a heap. It arranges elements in ascending (or descending) order by repeatedly removing the maximum (or minimum) element from the heap. The algorithm guarantees stability and has a consistent worst-case time complexity of O(n log n).
It follows a similar approach to selection sort, where the smallest element is repeatedly identified and placed at the beginning. The key idea behind heap sorting is to gradually remove elements from the heap and insert them into the sorted portion of the list. This algorithm is often called an in-place sorting algorithm since it rearranges the elements within the original array without requiring additional memory.
With the correct applications of HeapSort, developers can leverage these concepts and efficiently solve all problems -
Heap sort is utilised in general sorting where users can sort a list of items or arrays in descending or ascending order using the same. It can be effectively implemented to manage large datasets.
A priority queue is a data structure that allows efficient insertion, deletion, and extraction of elements based on their priority. Heap sorts are commonly used to implement priority queues because they provide fast operations such as insert(), delete(), extract max(), and decrease key() in O(log n) time.
Priority queues, implemented using binary heaps, are particularly useful in graph algorithms such as Dijkstra's Shortest Path and Prim's Minimum Spanning Tree. These algorithms require efficient extraction of the minimum (or maximum) element, which can be achieved using a priority queue based on a binary heap.
Heap data structures and heap-related operations can solve problems beyond sorting and priority queues. Heaps can be utilised in problems related to scheduling, event-driven simulations, network routing, job sequencing, data compression, and more.
Heapify is a recursive process to create a heap data structure from a binary tree represented as an array. It is responsible for establishing the heap property as a Min-Heap or Max-Heap. The process begins from the last index of the non-leaf node, which can be calculated as n/2 – 1, where n represents the total number of elements in the array. Using recursion, Heapify ensures that the heap property is maintained throughout the array.
Heapify works by satisfying the heap property for a given node in a heap data structure. It is commonly used to build a heap from an unordered array or to restore the heap property after an element has been inserted or modified.
Heapify compares a node with its children and swaps values if necessary to satisfy the heap property.
It starts with a binary tree represented as an array. Starting from the last non-leaf node, each node is recursively Heapified by comparing it with its children and swapping values if needed.
This process ensures the heap property is satisfied for the entire subtree rooted at each node.
By performing Heapify in reverse order, the array is transformed into a valid heap.
Heapify guarantees efficient extraction of the maximum (or minimum) element from the heap, with a time complexity of O(log n) for each operation.
A heap is called a min-heap if the key at the root node is less than or equal to the keys at its child nodes.
A heap is classified as a min-heap if the key at the root node is greater than or equal to the keys of its child nodes.
Let’s look at the Heap Sort algorithm -
#include <stdio.h>
// Function to swap two elements
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Heapify function to maintain the max-heap property
void heapify(int array[], int size, int index)
{
int largest = index; // Initialize the largest element as the root
int left = 2 * index + 1; // Left child index
int right = 2 * index + 2; // Right child index
// If left child is larger than root
if (left < size && array[left] > array[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < size && array[right] > array[largest]) {
largest = right;
}
// If largest is not the root, swap the root with the largest element
if (largest != index) {
swap(&array[index], &array[largest]);
// Recursively heapify the affected sub-tree
heapify(array, size, largest);
}
}
// Heap Sort function
void heapSort(int array[], int size)
{
// Build the max-heap from the array
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
}
// Extract elements from the heap one by one
for (int i = size - 1; i > 0; i--) {
// Move the current root (maximum element) to the end
swap(&array[0], &array[i]);
// Heapify the reduced heap
heapify(array, i, 0);
}
}
// Function to print an array
void printArray(int array[], int size)
{
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
// Driver code
int main()
{
int arr[] = {54, 32, 67, 12, 90, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, size);
heapSort(arr, size);
printf("Sorted array: ");
printArray(arr, size);
return 0;
} |
Let’s now look at an example of Heap Sort program in c with output -
Original array: 54 32 67 12 90 5 Sorted array: 5 12 32 54 67 90 |
In this heap sort example, the input array is {54, 32, 67, 12, 90, 5}. The program will first display the original array, and then after performing heap sort, it will display the sorted array.
Let’s understand the working of Heap Sort in a detailed explanation.
Start by considering the given array.
To build a max-heap, iterate from the last non-leaf node (n/2 - 1) to the root (0) in reverse order.
For each non-leaf node, perform the heapify operation to ensure that the largest element is at the subtree's root.
If necessary, Heapify compares the current node with its children and swaps values to satisfy the max-heap property.
After iterating through all non-leaf nodes, the array is transformed into a max-heap.
Perform sorting:
Start by swapping the max-heap's first element (root) with the array's last element.
Reduce the heap size by 1, excluding the last (sorted) element from future heapify operations.
Apply heapify to the reduced heap (excluding the sorted element) to ensure that the largest element is at the root again.
Repeat the above two steps (swapping and heapify) until the heap size becomes. This process progressively places the largest elements at the end of the array.
After the last iteration, the array will be sorted in ascending order.
The array is now sorted.
Let's walk through a heap sort example to illustrate the working of Heap Sort step-by-step:
Consider an array:
12, 11, 13, 5, 6, 7 |
Building the max-heap:
Repeating from the last non-leaf node (n/2 - 1 = 2) to the root (0):
At index 2: heapify(array, 6, 2) => [12, 11, 13, 5, 6, 7] (no swaps needed)
At index 1: heapify(array, 6, 1) => [12, 6, 13, 5, 11, 7] (swapped 11 with 6)
At index 0: heapify(array, 6, 0) => [13, 6, 12, 5, 11, 7] (swapped 11 with 13, and 12 with 6)
The array is now a max-heap: [13, 6, 12, 5, 11, 7]
Sorting the array:
Swap the first element (root) with the last element and reduce the heap size by 1:
[7, 6, 12, 5, 11, 13]
Apply heapify to the reduced heap:
heapify(array, 5, 0) => [12, 6, 7, 5, 11, 13] (swapped 11 with 12)
Swap the first element (root) with the last element and reduce the heap size by 1:
[11, 6, 7, 5, 12, 13]
Apply heapify to the reduced heap:
heapify(array, 4, 0) => [7, 6, 11, 5, 12, 13] (swapped 12 with 7)
Repeat the above steps until the heap size becomes 1:
[6, 5, 7, 11, 12, 13]
[5, 6, 7, 11, 12, 13]
The array is now sorted in ascending order: [5, 6, 7, 11, 12, 13].
Let’s take a look at a table explaining the time and space complexity in Heap Sort -
Complexity | Best Case | Average Case | Worst Case | Space Complexity |
Time Complexity | O(n log n) | O(n log n) | O(n log n) | O(1) |
Space Complexity | O(1) | O(1) | O(1) | O(1) |
The best-case scenario occurs when the input array is already a max-heap. In this case, the heapify operation will not need to be performed, resulting in a time complexity of O(n log n).
On average, Heap Sort has a time complexity of O(n log n). This is because both the building of the max-heap and the sorting phase require heapify operations, which have a time complexity of O(log n). These operations are performed n times in total.
The worst-case scenario for Heap Sort also has a time complexity of O(n log n). This occurs when the input array is in reverse order, requiring heapify operations at each step of the sorting phase.
Heap Sort has a space complexity of O(1) since the sorting is performed in place without requiring additional space that scales with the input size. Only constant additional space is needed for variables and function calls.
Here are some advantages of Heap Sort -
Heap Sort demonstrates impressive efficiency as the number of items to sort increases. Unlike other algorithms that experience exponentially slower performance, Heap Sort's time complexity grows logarithmically.
Heap Sort stands out for its minimal memory requirements. Besides the initial memory allocation needed to store the list of items to be sorted, Heap Sort does not require additional memory space.
One of the notable advantages of Heap Sort is its relative simplicity. It does not heavily rely on advanced computer science concepts, such as recursion.
Heap Sort comes with its own disadvantages -
Heap Sort is known for being resource-intensive. It may have a higher cost in terms of time and computational resources than other sorting algorithms.
Heap Sort is considered an unstable sorting algorithm. This means it may rearrange the relative order of elements with equal keys during the sorting process.
While Heap Sort is generally efficient for many scenarios, it may not be optimal when dealing with highly complex data structures. Other sorting algorithms might offer better performance in such cases.
Heap Sort is a powerful sorting algorithm in C programming that efficiently sorts an array by transforming it into a max heap and repeatedly extracting the maximum element. With its time complexity of O(n log n) and in-place sorting capability, Heap Sort offers an optimal solution for sorting large datasets. Its stability, simplicity, and minimal memory usage make it a valuable tool in various applications where efficiency and performance are paramount.
upGrad’s Executive Post Graduate Programme in Machine Learning & AI - Now with Generative AI lectures is the perfect course for developing in-demand skills like Machine Learning, Deep Learning, NLP, ChatGPT, Dall-E, Midjourney, Graph Neural Networks, and much more. This course will help students master advanced techniques and applications, which will help them advance their dream careers.
Heap Sort follows a two-phase approach. The array is transformed into a max heap in the first phase, ensuring the largest element is at the root. The highest element (root) is removed in the second phase, and the remaining elements are reorganised to create a new max heap.
Heap Sort is classified as an unstable sorting algorithm because its operations can alter the relative order of elements with equal keys. During the sorting process, the arrangement of equivalent keys may change, leading to potential rearrangements in the final sorted order.
Heap Sort is not an example of a "Divide and Conquer" algorithm. Heap Sort utilises a heap data structure to perform its sorting operations efficiently. It does not involve dividing the array into smaller subproblems and recursively solving them.
Leave a Reply
Your email address will not be published. Required fields are marked *