C Program To Sort 5 Numbers Using Heap Sorting Methodology

Sorting a small set of numbers is a fundamental task in computer science. In this article, you will learn how to efficiently sort five numbers using the Heap Sort algorithm in C, understanding its mechanics and implementation.

Problem Statement

The challenge is to arrange a given set of five unsorted numbers into ascending order. While simple comparison sorts work for small arrays, for larger datasets, more efficient algorithms like Heap Sort offer better performance characteristics by leveraging a specific tree-based data structure known as a heap.

Example

Consider the following unsorted array of five numbers: [4, 1, 3, 2, 5]

After applying the Heap Sort algorithm, the numbers will be sorted in ascending order: [1, 2, 3, 4, 5]

Background & Knowledge Prerequisites

To effectively understand and implement Heap Sort, a reader should have a basic grasp of the following concepts:

• C Language Basics: Understanding of arrays, loops, functions, and pointers.
• Binary Trees: Familiarity with the concept of a tree data structure where each node has at most two children.
• Complete Binary Trees: A binary tree in which all levels are completely filled except possibly the last level, and all nodes in the last level are as far left as possible. Arrays can represent complete binary trees efficiently.
• Heaps: A specialized tree-based data structure that satisfies the heap property. For a max-heap, the value of each node is greater than or equal to the value of its children.

Use Cases or Case Studies

Heap Sort and the underlying heap data structure are valuable in several practical scenarios:

• Priority Queues: Heaps are the fundamental data structure for implementing priority queues, where elements are retrieved based on their priority (e.g., in operating system process scheduling or event simulations).
• System Reliability: In systems that require finding the k-th largest or smallest element efficiently, heaps can provide a solution without fully sorting the entire dataset.
• External Sorting: When data to be sorted is too large to fit into memory, heap sort principles can be adapted for external sorting algorithms, which process data in chunks.
• Graph Algorithms: Heaps are used in graph algorithms like Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm for efficiently managing edges or vertices with minimum weights.
• Selection Algorithms: For tasks such as finding the median or selecting a specific percentile from a large dataset, heap-based approaches can be more efficient than full sorting.

Solution Approaches

Heap Sort is a comparison-based sorting algorithm that uses a binary heap. It can be thought of as a two-stage algorithm: building a max-heap from the input data, and then repeatedly extracting the maximum element from the heap.

Approach 1: Implementing Heap Sort

Heap Sort leverages the heap data structure to efficiently sort elements. It primarily consists of a heapify function and the main heapSort logic.

• One-line summary: Build a max-heap from the array and then repeatedly swap the root (largest element) with the last element, reducing the heap size, and re-heapifying the new root.

// Heap Sort for 5 Numbers
#include <stdio.h>

// Function to heapify a subtree rooted with node i
// n is size of heap
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) {
        // Swap
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

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

// Main function to do heap sort
void heapSort(int arr[], int n) {
    // Step 1: Build a max-heap (rearrange array)
    // Start from the last non-leaf node and heapify downwards
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Step 2: One by one extract an element 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 max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    // Step 1: Define the array of 5 numbers
    int arr[] = {4, 1, 3, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    // Step 2: Apply Heap Sort
    heapSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

• Sample Output:

Original array: 4 1 3 2 5 
Sorted array: 1 2 3 4 5

• Stepwise Explanation:

1. heapify(arr, n, i) Function:

• This function takes an array arr, its size n, and an index i (the root of the subtree to heapify).
• It assumes that the left and right children of i are already heapified. Its job is to make arr[i] conform to the max-heap property.
• It compares arr[i] with its left and right children.
• If a child is larger than arr[i], it swaps arr[i] with the largest child.
• After a swap, the heapify function is recursively called on the affected subtree to ensure the max-heap property is maintained down the tree.

1. heapSort(arr, n) Function:

• Build Max-Heap: The first loop (for (int i = n / 2 - 1; i >= 0; i--)) iterates from the last non-leaf node up to the root (index 0). For each node, it calls heapify. This process effectively converts the entire array into a max-heap, where the largest element is at arr[0].
• Extract Elements: The second loop (for (int i = n - 1; i > 0; i--)) extracts elements one by one.
• It swaps the root of the heap (arr[0], which is the largest element) with the last element of the current heap (arr[i]).
• This moves the largest element to its correct sorted position at the end of the array.
• It then calls heapify on the reduced heap (size i) starting from the new root (index 0) to re-establish the max-heap property for the remaining elements.

1. main() Function:

• An array of five unsorted integers is initialized.
• The printArray function displays the original array.
• heapSort is called to sort the array.
• Finally, printArray displays the sorted array.

Conclusion

Heap Sort is an efficient, comparison-based sorting algorithm with a time complexity of O(N log N) in all cases (best, average, and worst). It sorts in-place, meaning it requires a minimal amount of additional memory (O(1) auxiliary space). By understanding the heapify operation and the two-phase approach (build heap, extract elements), you can effectively sort arrays using this robust algorithm.

Summary

• Heap Sort is an efficient, in-place sorting algorithm with O(N log N) time complexity.
• It leverages a binary heap data structure, specifically a max-heap for ascending order.
• The algorithm involves two main stages: building a max-heap from the input array and repeatedly extracting the maximum element.
• The heapify function is crucial for maintaining the heap property after insertions or deletions.
• Heap Sort is suitable for both small and large datasets and finds applications in priority queues, system scheduling, and selection problems.