C++ Program To Sort 5 Numbers Using Heap Sorting Methodology

Sorting numbers is a fundamental operation in computer science, crucial for organizing data efficiently. In this article, you will learn how to implement the heap sort algorithm to sort a small set of five numbers using C++.

Problem Statement

The challenge is to take an unordered list of five numbers and arrange them in ascending order. While this specific problem might seem simple for such a small dataset, understanding an efficient sorting algorithm like heap sort provides valuable insights for handling larger and more complex data structures. The goal is to transform an initial sequence like [4, 1, 3, 2, 5] into [1, 2, 3, 4, 5].

Example

Consider the unsorted numbers: [4, 1, 3, 2, 5]. After applying the heap sort algorithm, the numbers will be arranged in ascending order: [1, 2, 3, 4, 5].

Background & Knowledge Prerequisites

To effectively understand heap sort, familiarity with a few core concepts is beneficial:

• C++ Basics: Understanding variables, arrays, functions, loops, and basic input/output operations.
• Arrays/Vectors: How to declare, initialize, and manipulate one-dimensional arrays or std::vector in C++.
• Binary Trees: A conceptual understanding of binary trees, where each node has at most two children.
• Heaps: Specifically, a binary heap, which is a complete binary tree that satisfies the heap property.
• Max-Heap: For any given node i, the value of i is greater than or equal to the values of its children. The largest element is always at the root.
• Min-Heap: For any given node i, the value of i is less than or equal to the values of its children. The smallest element is always at the root.

Use Cases or Case Studies

Heap sort, while less common than quicksort or merge sort for general-purpose sorting due to its slightly higher constant factor, has distinct advantages in specific scenarios:

• Priority Queues: Heaps are the underlying data structure for efficient priority queue implementations, where elements are extracted based on priority.
• System Stability: Heap sort is an in-place sorting algorithm, meaning it requires a minimal amount of additional memory, making it suitable for systems with limited memory resources.
• Guaranteed Performance: Unlike quicksort, whose worst-case performance is O(n^2), heap sort has a guaranteed O(n log n) time complexity, making it a reliable choice when consistent performance is critical.
• Large Datasets: For very large datasets that might not fit entirely into cache, heap sort's memory access pattern can be more predictable than some other algorithms.

Solution Approaches

Heap sort works by transforming the input array into a max-heap, then repeatedly extracting the largest element from the heap and placing it at the end of the array.

Implementing Heap Sort for 5 Numbers

Heap sort efficiently sorts an array by first building a max-heap from the array elements and then repeatedly extracting the maximum element (the root of the heap), placing it at the end of the unsorted part of the array, and rebuilding the heap.

// Heap Sort for 5 Numbers
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Function to heapify a subtree rooted with node i
// n is size of heap
void heapify(std::vector<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) {
        std::swap(arr[i], arr[largest]);

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

// Main function to do heap sort
void heapSort(std::vector<int>& arr, int n) {
    // Step 1: Build a max-heap (rearrange array)
    // Iterate from the last non-leaf node up to the root
    // (n/2 - 1) is the index of the last non-leaf node
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Step 2: One by one extract an element from heap
    // After building the max-heap, the largest element is at the root (index 0).
    // Swap it with the last element of the heap, then reduce the heap size
    // and heapify the new root.
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        std::swap(arr[0], arr[i]);

        // Call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Define the array of 5 numbers
    std::vector<int> numbers = {4, 1, 3, 2, 5};
    int n = numbers.size();

    std::cout << "Original array: ";
    printArray(numbers);

    // Step 2: Apply heap sort
    heapSort(numbers, n);

    std::cout << "Sorted array: ";
    printArray(numbers);

    return 0;
}

Run

Sample Output

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

Stepwise Explanation

1. heapify Function:

• This function takes an array, its size n, and an index i. Its job is to ensure that the subtree rooted at i satisfies the max-heap property.
• It compares the element at i with its left (2*i + 1) and right (2*i + 2) children.
• If any child is larger than the current largest element (initially arr[i]), largest is updated to the child's index.
• If largest is no longer i, it means the root wasn't the largest. We swap arr[i] with arr[largest] and then recursively call heapify on the affected subtree to maintain the max-heap property down the tree.

1. heapSort 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 (n/2 - 1 is the index of the last node that can have children). For each such node, it calls heapify to ensure its subtree is a max-heap. After this loop completes, the entire array is transformed into a max-heap, meaning 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 current root (arr[0], which is the largest element) with the last element of the unsorted part of the array (arr[i]).
• The largest element is now in its correct sorted position at the end of the array.
• The effective size of the heap is reduced by one (i).
• Finally, heapify is called on the new root (arr[0]) to restore the max-heap property for the remaining i elements. This process continues until all elements are sorted.

1. main Function:

• An std::vector named numbers is initialized with the five unsorted values.
• The printArray function displays the original content.
• heapSort is called with the vector and its size.
• printArray is called again to display the sorted vector.

Conclusion

Heap sort is a robust, comparison-based sorting algorithm known for its guaranteed O(N log N) time complexity. By leveraging the heap data structure, it efficiently sorts elements by repeatedly extracting the largest element. While it might involve more swaps than some other algorithms, its in-place nature and consistent performance make it a valuable tool in various programming scenarios, even for small datasets like five numbers.

Summary

• Heap sort uses a binary heap data structure to sort an array.
• It operates in two main phases: building a max-heap from the array and then repeatedly extracting the maximum element.
• The heapify function is crucial for maintaining the heap property throughout the sorting process.
• Heap sort has a time complexity of O(N log N) in all cases (best, average, worst).
• It is an in-place sorting algorithm, requiring minimal additional memory.