Heap Sort Code in C: What is and Program
Heap sort in C is renowned for its O(n log n) efficiency and ability to sort in place without extra memory. It capitalizes on the properties of a heap to perform sorting, first transforming the array into a heap and then sorting it by repeatedly removing the root element and re-heapifying the remaining elements.
Heap sort in C is an efficient comparison-based sorting algorithm that organizes data into a binary heap structure, allowing for efficient retrieval and removal of the maximum or minimum element. It first builds a heap from the input data and then repeatedly extracts the top element, resulting in a sorted array. Let's understand this essential C programming concept with examples.
Explore: Online C Programming Courses and Certifications
Table of Content
- How Does Heap Sort Work?
- Algorithm
- Real-World Application
- Advantages of Heap Sort
- Disadvantages of Heap Sort
How Does Heap Sort Work?
Heap Sort is an algorithm that capitalizes on the properties of a heap to sort an array. A heap is a special tree-based data structure that satisfies the heap property.
- Creating a Heap: The first phase involves building a heap from the input data.
- Sorting: Once the heap is created, the elements are repeatedly removed from the heap and placed into the array in sorted order.
The heap property ensures that the parent node is greater than or equal to (in a max heap) or less than or equal to (in a min-heap) the child nodes. In the context of sorting, we use a max heap to sort the data in ascending order.
Illustration:
To visualize Heap Sort, consider:
- You have a set of building blocks of different sizes.
- These blocks are arranged into a pyramid shape, satisfying the heap condition—every block must be smaller than the block below it.
- We then take the top of the heap (the largest block) and move it to the foundation of a new building, creating a sorted structure.
- This process continues until all blocks are moved from the heap to the new building, resulting in a sorted order.
Heap Sort is a popular sorting algorithm that organizes elements by first turning the list into a Max Heap (a complete binary tree where each node is greater than its children). The algorithm then repeatedly swaps the first value of the heap with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This process continues until the range of considered values is one.
Read Later
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Algorithm
Step 1: Create a binary tree of the array.
Step 2: Build a heap:
Arrange the array elements into a max-heap (largest element at the root) or a min-heap (smallest element at the root).
Step 3: Repeatedly extract and place:
Extract the root element (the largest/smallest) from the heap and place it at the end of the sorted array.
Heapify the remaining elements to maintain the heap property.
Step 4: Repeat until sorted:
Continue extracting and placing elements until the heap is empty, resulting in a sorted array.
Step 1: Initial Max Heap Creation
We start with an array [5, 11, 4, 6, 2] that we want to sort. The first step in Heap Sort is to create a Binary Tree out of the array. Then we generate the Max Heap from the Binary Tree created.
Max Heap:
Step 2: Heapify
After the Max Heap is formed, the root of the heap (which is the maximum element in the heap) is swapped with the last element of the array. And the then the root (max element) is removed. The Max Tree is created again. We keep doing this until the last element is popped.
Pass 1:
Pass 2:
Pass 3:
Pass 4:
Step 3: Sorted Array
A sorted array [2, 4, 5, 6, 11] would be the final outcome after completing the Heap Sort process. The elements are sorted in ascending order.
Each step in Heap Sort involves ensuring that the heap property is maintained as elements are swapped and moved to their correct sorted position.
Dry Run
| Pass |
Heap (Max Heap) |
Array After Heapify |
Max Element |
| 0 |
[5, 11, 4, 6, 2] |
[11, 6, 4, 5, 2] |
11 |
| 1 |
[6, 5, 4, 2] |
[6, 5, 4, 2, 11] |
6 |
| 2 |
[5, 2, 4] |
[5, 2, 4, 6, 11] |
5 |
| 3 |
[4, 2] |
[4, 2, 5, 6, 11] |
4 |
| 4 |
[2] |
[2, 4, 5, 6, 11] |
2 |
Pseudo Code:
To outline the steps in C, let's first draw out the pseudo-code:
function heapify(array, n, i) {
// Create a heap
// Placeholder for heapify logic
}
function heapSort(array, n) {
// Build a heap from the array
// Placeholder for building heap logic
// One by one, extract elements from the heap
// Placeholder for extracting elements logic
}
Code (C) with proper comments:
Now let's translate this outline into C, with helpful commentary:
// Function to build a heap from the arrayvoid heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root if (l < n && arr[l] > arr[largest]) { largest = l; }
// If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) { largest = r; }
// If largest is not root if (largest != i) { swap(arr[i], arr[largest]); // Swap the root with the largest
// Recursively heapify the affected sub-tree heapify(arr, n, largest); }}
// Function to perform heap sortvoid heapSort(int arr[], int n) { // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }
// One by one, extract elements from heap for (int i = n - 1; i > 0; i--) { // Move current root to end swap(arr[0], arr[i]);
// Call max heapify on the reduced heap heapify(arr, i, 0); }}
Time Complexity
The efficiency of an algorithm is often measured by its time complexity, which represents the amount of time an algorithm takes to complete as a function of the length of the input.
- Creating the Heap: The process of creating a heap from an unsorted array takes O(n) time. This is a one-time setup done at the beginning.
- Heapify Operations: Each heapify operation, which is the core of the algorithm, takes O(log n) time because it follows the height of the tree (heap), and a heap has a height of log n.
- Sorting the Array: For each of the n elements, a heapify operation is called after removing the root of the heap, leading to a total time of n * O(log n).
Considering these steps together, the overall time complexity of Heap Sort is O(n log n).
Space Complexity
Space complexity measures the total amount of memory or space taken up by an algorithm about the input size.
- In-Place Sorting: Heap Sort is an in-place algorithm, meaning that apart from the original array, it requires a constant amount of additional space for variables used in the algorithm. Therefore, its space complexity is O(1).
Real-World Application
Let's consider a real-world scenario explaining the Heap Sort Code in C where we have a list of students and their respective scores in a class. The task is to sort this list of students based on their scores using the Heap Sort algorithm.
Task:
Sort a list of students based on their scores in a class using the Heap Sort algorithm.
Solution Approach:
- Create a data structure to represent students including their names and their scores.
- Use the Heap Sort algorithm to sort the list of students based on their scores.
- Heapify the student list to build a max heap, ensuring that the student with the highest score becomes the root of the heap.
- Extract the students from the max heap one by one to obtain a sorted list of students in descending order of score.
#include <stdio.h>#include <stdlib.h>#include <string.h>
// Structure to represent a student with name and scoretypedef struct Student { char name[50]; int score;} Student;
// Function to perform max heapifyvoid maxHeapify(Student students[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2;
if (left < n && students[left].score > students[largest].score) largest = left;
if (right < n && students[right].score > students[largest].score) largest = right;
if (largest != i) { // Swap students[i] and students[largest] Student temp = students[i]; students[i] = students[largest]; students[largest] = temp;
maxHeapify(students, n, largest); }}
// Function to perform heap sortvoid heapSort(Student students[], int n) { // Build max heap for (int i = n / 2 - 1; i >= 0; i--) maxHeapify(students, n, i);
// Extract students from max heap (sorting) for (int i = n - 1; i > 0; i--) { // Swap students[0] and students[i] Student temp = students[0]; students[0] = students[i]; students[i] = temp;
maxHeapify(students, i, 0); }}
// Function to swap two studentsvoid swap(Student *a, Student *b) { Student temp = *a; *a = *b; *b = temp;}
int main() { Student classScores[] = { {"Alice", 85}, {"Bob", 72}, {"Charlie", 93}, {"David", 65}, {"Emily", 78}, }; int n = sizeof(classScores) / sizeof(classScores[0]);
printf("Unsorted list of students and their scores:\n"); for (int i = 0; i < n; i++) { printf("%s: %d\n", classScores[i].name, classScores[i].score); }
heapSort(classScores, n);
printf("\nSorted list of students based on scores (Descending order):\n"); for (int i = 0; i < n; i++) { printf("%s: %d\n", classScores[i].name, classScores[i].score); }
return 0;}
Output:
Unsorted list of students and their scores:
Alice: 85
Bob: 72
Charlie: 93
David: 65
Emily: 78
Sorted list of students based on scores (Descending order):
Charlie: 93
Alice: 85
Emily: 78
Bob: 72
David: 65
Advantages of Heap Sort:
- Efficient for large datasets: With a time complexity of O(n log n) on average and worst-case, Heap Sort performs well for sorting large arrays.
- In-place sorting: It requires no additional memory space beyond the original array, making it efficient for memory-constrained environments.
- Not recursive: Unlike algorithms like Quicksort, Heap Sort avoids the risk of stack overflow for very large datasets due to its iterative nature.
- Priority queues: The underlying heap structure can be used efficiently for implementing priority queues, where the element with the highest priority is accessed quickly.
Disadvantages of Heap Sort:
- More complex to implement: Compared to simpler algorithms like Insertion Sort, Heap Sort requires understanding and implementing the heap data structure and its operations.
- Not stable: Heap Sort does not preserve the original order of elements with equal keys, which might be important in certain applications.
- Constant factors: While the time complexity is theoretically good, the constant factors involved in heap operations can make it slightly slower than other sorting algorithms in practice for smaller datasets.
Conclusion!!
Heap Sort is akin to an architect methodically organizing a complex blueprint. It offers a blend of efficiency and simplicity, making it a reliable choice for various applications. With its robust performance on large datasets and minimal space requirements, Heap Sort is an essential tool in the programmer's arsenal. By mastering Heap Sort in C, one can efficiently tackle a myriad of sorting challenges, bringing order and structure to data in a way that is as timeless as the foundations of architecture itself.
Contributed By: Manali Bhave
Top FAQs on Heap Sort
Why is Heap Sort not as popular as Quick Sort despite having the same time complexity?
Heap Sort typically has a higher constant factor in its running time than Quick Sort. Moreover, Quick Sort has better cache performance and can be easily optimized for different systems, making it generally faster in practice.
Is Heap Sort stable?
No, Heap Sort is not a stable sort. During the 'heapify' process, it can change the relative order of equal elements.
Can Heap Sort be optimized for better performance?
While the basic algorithm has a fixed complexity, certain optimizations like building an initial heap using the bottom-up method can reduce the constants involved in the sorting process.
How does Heap Sort handle duplicate values?
Duplicate values are treated the same as unique values in Heap Sort. They are placed in their correct position with respect to the heap property, maintaining the algorithm's integrity.
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
