Heap Sort in C

Heap Sort in C: An introduction and implementation.

Heap Sort is a Comparison-based sorting algorithm that falls under the category of selection sorts. It is based on a binary heap data structure and is known for fixing efficiency in sorting large data sets. In this article, we will learn the concept of Heap Sort and provide a step-by-step guide on how to implement Heap Sort in C programming language.

Understanding Heap Sort

Before diving into the coding aspect, it is essential to understand what a heap is and how Heap Sort works. A heap is a complete binary tree where each parent node is either greater than or equal to (in a max heap) or less than or equal to (in a min-heap) its child nodes. The Heap Sort algorithm leverages the properties of a heap to sort data in either ascending or descending order.

The Heap Sort process can be divided into two main phrases.

• Building a Heap from input data.
• Reapeaditly removing the maximum element from the Heap(In max heap) or the minimum element( In a min heap) and then maintaining the heap property.

Implementing Heap Sort in C

Here is a step-by-step guide on how to implement Heap Sort in C programming language.

Heapify

This function is used to maintain the Heap property. It ensures that the subtree rooted at a given index follows the Heap property. If the children of a node are greater (in a max heap) or smaller(in a min-heap) than the node, We need to swap and continue heapfing.

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

BuildHeap

This function builds a heap from a given array. It calls the heapify function starting from the last non-leap node all the way to the root node.

void buildHeap(int arr[], int n)
{
    int startIndex = (n / 2) - 1;
    for (int i = startIndex; i >= 0; i--)
    {
        heapify(arr, n, i);
    }
}

HeapSort

This is the main function that implement Heap Sort. After building the Heap, it removes the elements one by one from the Heap a nd then heapifies the remaining elements.

 void heapSort(int arr[], int n)
{
    // Build Heap (rearrange array)
    buildHeap(arr, n);
    for (int i = n - 1; i > 0; i--)
    {
        swap(&arr[0], &arr[i]); // Move current root to end
        // call max heapify on the reduced heap.
        heapify(arr, i, 0);
    }
}

Swap

This is a utility function that swaps two elements in the array.

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Complete C Program for Heap Sort

#include <stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void heapify(int arr[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}
void buildHeap(int arr[], int n)
{
    int startIndex = (n / 2) - 1;
    for (int i = startIndex; i >= 0; i--)
    {
        heapify(arr, n, i);
    }
}
void heapSort(int arr[], int n)
{
    // Build Heap (rearrange array)
    buildHeap(arr, n);
    for (int i = n - 1; i > 0; i--)
    {
        swap(&arr[0], &arr[i]); // Move current root to end
        // call max heapify on the reduced heap.
        heapify(arr, i, 0);
    }
}
void main()
{
    int arr[] = {6, 7, 8, 4, 2, 67, 23, 56};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Array before sorting\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    heapSort(arr, n);
    printf("\nArray after sorting\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
}

Output

Heap Sort is a powerful sorting algorithm that is particularly useful for large data sets. The implementation of Heap Sort in C demonstrates how to manipulate elements within an array to sort them efficiently. By understanding the principle behind Heap Sort and following the implementation steps you can integrate this dorting algorithm into your C project to improve data handling and sorting efficiently.

Happy Coding & Learning

See Also

• Selection Sort in C
• Quick Sort in C