C++ • SORTING ALGORITHM Heap Sort

C++ • SORTING ALGORITHM

Heap Sort

ALGORITHM

Heap Sort

TIME COMPLEXITY

O(n log n)

SPACE COMPLEXITY

O(1)

ORDER

Ascending

C++ Implementation

heap_sort.cpp

#include <iostream>
using namespace std;

class ArraySort
{
    int n;
    int a[100];

    // To heapify a subtree rooted with node i
    void heapify(int n, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

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

        if (right < n && a[right] > a[largest])
            largest = right;

        if (largest != i)
        {
            swap(a[i], a[largest]);
            heapify(n, largest);
        }
    }

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Heap Sort function
    void heapSort()
    {
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(n, i);

        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--)
        {
            swap(a[0], a[i]);
            heapify(i, 0);
        }
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.heapSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
5 3 4 1 2

Output

Sorted Array:
1 2 3 4 5

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

class ArraySort

Creates a class named ArraySort containing the array and sorting methods.

int n;

Stores the total number of elements in the array.

int a[100];

Declares an integer array capable of holding up to 100 elements.

void heapify(int n, int i)

Maintains the max-heap property for a subtree rooted at index i.

ArraySort()

Class constructor that initializes object properties when instantiated.

n = 0;

Initializes the array size variable to zero.

void input()

Reads the array size and elements from the user.

for (int i = n / 2 - 1; ...)

Builds a max-heap from the bottom up starting from the last non-leaf node.

swap(a[0], a[i]);

Moves the largest element (root) to the end of the current unsorted portion.

heapify(i, 0);

Restores the max-heap property on the reduced heap of size i.

void output()

Displays the final sorted array to the console.

ArraySort obj;

Instantiates the ArraySort object and triggers the constructor.

return 0;

Signals successful program execution.

How heap sort works: Heap sort is a comparison-based sorting technique based on a Binary Heap data structure. It divides its workspace into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element from the heap and placing it at the end of the array.