Heap Sort Program in C - Naukri Code 360

Q: Which method is used in heap sort?

Heap Sort uses the "heapify" method to maintain the heap property while repeatedly extracting the root element to build the sorted array.

Introduction

Heap sort 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 the maximum element at the end. We repeat the same process for the remaining elements. What sets heap sort apart is its ability to efficiently find the largest (or smallest, depending on the heap type) element.

In this article, we will learn how heap sort works, implement it in C, analyze its complexity, & discuss its advantages & disadvantages.

Algorithm of Heap Sort in C

Heap sort is a powerful algorithm for sorting arrays & it operates in two major phases: building a heap & then extracting elements from the heap to achieve a sorted array. Initially, the unsorted array is transformed into a heap structure, which is a complete binary tree where every parent node is either greater than or equal to its child nodes (in the case of a max heap) or less than or equal to its child nodes (in a min heap). This setup is crucial as it lets the largest or smallest element (depending on max or min heap) to be positioned at the root of the heap.

Step-by-Step Process

Build a Max Heap from the input data:
Start from the last non-leaf node & adjust the heap structure from bottom to top. The idea is to ensure that each parent node is greater than its child nodes.
Extract the Maximum Element:
Swap the root of the heap (the largest element) with the last element of the heap.
Reduce the size of the heap by one so that the last element is kept in its correct place.
Now, float down the new root element to maintain the heap property by swapping it with its largest child until the heap property is restored.
Repeat the process:
Continue removing the largest element from the heap & reducing its size until all elements have been sorted.

The transformation from a random array into a heap is the core mechanism that makes heap sort efficient. This approach leverages the properties of heaps, ensuring that with each extraction of the root element, the remaining elements can quickly be reorganized into a heap. The continuous maintenance of the heap structure after each removal is what effectively drives the sorting process.

Implementation of Heap Sort in C

The implementation involves creating functions to handle the array manipulations necessary to maintain the heap property and perform the sort. We will break down the process into manageable functions to build the heap, adjust it, and perform the sorting.

C

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify a subtree rooted with node i
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left = 2*i + 1
    int right = 2 * i + 2; // right = 2*i + 2

    // 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) {
        swap(&arr[i], &arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Function to perform heap sort
void 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);
    }
}

// Main function to test above functions
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array is \n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Sorted array is 
5 6 7 11 12 13

Explanation of the Code

The swap() function exchanges the values of two integers.
The heapify() function is the core of heap operations. It ensures that the heap properties are maintained, adjusting the tree if the children of the node i are larger than i.
The heapSort() function organizes the array into a heap and then extracts the elements in order to sort them. Initially, it builds a max heap from the unsorted array, and then it repeatedly removes the root to the end of the array and reduces the heap size for the remaining unsorted portion.
The main() function sets up an array, calls the heapSort() function, and prints the sorted array.

Complexity Analysis of Heap Sort

Learning and understanding the complexity of heap sort is crucial for evaluating its efficiency in different scenarios. The time complexity of heap sort has three major components: the time to build the initial heap, the time required for heap adjustments during extraction phases, and the overall time complexity.

Building the Initial Heap

The process of building a heap from an unsorted array takes O(n) time. This might seem counterintuitive because adjusting the heap at each node appears to take O(log n) time, and doing this for n nodes would suggest a complexity of O(n log n). However, a closer analysis shows that the nodes near the bottom of the tree are numerous but require fewer adjustments, and the higher levels, while requiring more work, are exponentially fewer. This balances out to linear time.

Adjustments During Extraction

Each time the root element is removed and the heap is adjusted (heapified), the time taken is O(log n) because we might need to adjust elements down the height of the tree. Since each removal is followed by a heapify operation, and there are n such operations, this part contributes O(n log n) to the overall complexity.

Overall Time Complexity

Combining these, while the initial heap building is O(n) and each of the n deletions takes O(log n) time, the total time complexity of heap sort is O(n log n).

Space Complexity

Heap sort is an in-place sorting algorithm. It does not require additional storage which means its space complexity is O(1). This is advantageous when dealing with large datasets where additional memory allocation could be costly.

Worst, Best, and Average Cases

The beauty of heap sort is its consistency. The worst-case time complexity is O(n log n), and so are the best and average cases. Unlike some other sorting algorithms that can perform better or worse depending on the initial arrangement of the data, heap sort maintains its performance regardless of the initial state of the array.

Heap sort's time complexity makes it suitable for applications where a consistent sorting time is valuable, but it might not always compete with faster algorithms like quicksort, especially in cases where the average case is more relevant. However, its space efficiency and predictable execution time are significant benefits.

Important Points about Heap Sort

When studying heap sort, it's essential to look at some of its key characteristics and considerations. Here are several important points that highlight the unique aspects of heap sort and its application:

Non-Stable Sorting

Heap sort does not ensure that the relative order of elements with identical keys is preserved. This occurs because as the heap is built and adjusted, elements with the same value might switch places in the process. In contexts where records are sorted by multiple keys, or where the original order has semantic importance, this could introduce issues or require additional handling.

In-Place Algorithm

Heap sort is performed within the original array with no need for additional storage space, making it an in-place algorithm. This characteristic is highly beneficial in environments with limited memory resources, such as embedded systems or applications dealing with large data sets on hardware with restricted memory capabilities.

Non-Adaptive Sorting

The performance of heap sort remains consistent regardless of the initial order of the input data. This means that even if the input array is partially sorted, heap sort will not capitalize on this fact and will perform the full sorting process. While this leads to predictable execution times, it does not offer efficiencies found in adaptive sorting algorithms that optimize performance based on initial input order.

Data Sensitivity

Despite its O(n log n) time complexity in all cases, the specifics of how data is distributed can affect the number of comparisons and swaps required during the sort. Elements that are closer to their final sorted position can reduce the need for swaps, slightly enhancing efficiency, but the overall time complexity remains dominated by the log-linear characteristics of the heap operations.

Excellent for Large Data Sets

Due to its low memory usage and consistent performance across different types of input data, heap sort is well-suited for large-scale sorting tasks. It can handle large arrays efficiently because it does not require additional memory proportional to the size of the input, unlike algorithms like merge sort, which require temporary arrays for merging.

Not the Fastest for Smaller or Complex Datasets

While heap sort is reliable for large data sets, it might not always be the best choice for smaller or more complex datasets where other sorting algorithms, like quicksort or mergesort, could perform faster. These algorithms might offer better average-case performance or stability, which are beneficial when working with datasets that benefit from adaptive sorting techniques or where maintaining the original order is critical.

Advantages of Heap Sort

Time Complexity Consistency

Heap sort provides a consistent time complexity of O(n log n) for all cases—best, average, and worst. This predictability is a significant advantage in scenarios where consistent performance is crucial, such as real-time processing systems where predictable timing is essential.

Space Efficiency

One of the most compelling features of heap sort is its space efficiency. As an in-place sorting algorithm, it requires no additional memory beyond what is needed to store the array. This minimal memory footprint makes it suitable for applications where memory space is constrained or where large data sets need to be sorted.

Not Sensitive to Input Size

Heap sort is well-suited for handling large datasets because its performance doesn’t degrade as the size of the input grows. This characteristic is particularly beneficial in back-end systems that need to handle variable and potentially very large datasets efficiently.

No Additional Memory for Merging

Unlike merge sort, heap sort does not require additional memory for merging elements. This makes heap sort more suitable for environments with limited memory resources where allocating additional arrays for sorting would be impractical.

Handles Complete Data Structures Efficiently

Since heap sort is based on a binary heap—a complete binary tree—it efficiently manages these structures, making it a natural choice for sorting data already organized in this way. This efficiency is particularly useful in priority queue implementations, where elements need to be frequently inserted and removed in sorted order.

Useful for Priority Queues

The operations of heap sort align well with those required for priority queue management, such as insertion at the end and deletion from the beginning of the array. This alignment makes heap sort an excellent choice for applications that involve priority queue operations, including various simulations, scheduling applications, and the implementation of certain graph algorithms.

Disadvantages of Heap Sort

Slower Compared to Some Other Sorts

Despite its consistent O(n log n) time complexity, heap sort is often slower in practice compared to other O(n log n) sorting algorithms like quicksort, especially on average. This is due to the overhead involved in maintaining the heap structure, which includes more swaps and comparisons than are typically needed in more optimized algorithms.

Non-Stable Sorting

Heap sort does not preserve the order of equal elements. In scenarios where the relative order of the same elements carries importance—such as when secondary attributes are being sorted—this lack of stability can be a significant drawback.

Non-Adaptive

Heap sort does not adapt to the existing order of elements. Its performance does not improve even if the input array is already partially or completely sorted, which can lead to inefficient sorting in practical applications where data may often come partially sorted.

Complex Implementation

Compared to other sorting algorithms like insertion sort or even quicksort, the implementation of heap sort is more complex due to the mechanisms of heap maintenance. This complexity can lead to higher development and maintenance costs, particularly when developers are less familiar with heap structures.

Not the Most Intuitive Approach

The concept of a binary heap and the logic behind heap operations are not as intuitive as those of simpler, more direct sorting algorithms. This lack of intuitiveness can make heap sort harder to understand and teach, potentially increasing the learning curve for new developers or students.

Poor Locality of Reference

Heap sort can have poor cache performance because it frequently accesses widely separated elements of the array, especially during the heapify operations. This poor locality of reference can lead to increased cache misses and reduced performance on modern computing architectures where memory access speed is a bottleneck.

Frequently Asked Questions

What is Heap Sort Program in C?

Heap Sort is a comparison-based sorting algorithm in C that builds a binary heap from the array and then repeatedly extracts the maximum (or minimum) element to sort the array.

What is heap in C with example?

A heap in C is a complete binary tree used to implement priority queues. It can be a max-heap or min-heap. For example, a max-heap maintains the largest element at the root.

Which method is used in heap sort?

Heap Sort uses the "heapify" method to maintain the heap property while repeatedly extracting the root element to build the sorted array.

Conclusion

In this article, we have learned the heap sort algorithm in detail. We discussed how it operates by building a binary heap and systematically removing the largest or smallest element (depending on the heap type) to sort the array. We covered its implementation in C, analyzed its time and space complexity, and highlighted important characteristics such as being an in-place and non-stable algorithm. We also talked about its advantages, such as its suitability for large datasets and consistent time complexity, and its disadvantages, including its relative slowness compared to other sorting algorithms and its complexity in implementation.

You can refer to our guided paths on the Code360. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.