Heap Sort Algorithm in C++

Heap sort is a sorting algorithm based on comparing elements in a Binary Heap data structure. We first find the maximum element and place it at the end. We repeat the same process for all the remaining elements.

// Heap Sort

#include <iostream>
using namespace std;

void createHeap(int arrayOfNumbers[], int numberOfElements, int i)
{
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < numberOfElements && arrayOfNumbers[left] > arrayOfNumbers[largest])
    {
        largest = left;
    }

    if (right < numberOfElements && arrayOfNumbers[right] > arrayOfNumbers[largest])
    {
        largest = right;
    }

    // If largest is not the root
    if (largest != i)
    {
        swap(arrayOfNumbers[i], arrayOfNumbers[largest]);
        createHeap(arrayOfNumbers, numberOfElements, largest);
    }
}

void heapSort(int arrayOfNumbers[], int numberOfElements)
{
    // Build the heap
    for (int i = numberOfElements / 2 - 1; i >= 0; i--)
    {
        createHeap(arrayOfNumbers, numberOfElements, i);
    }

    // Extract elements one by one
    for (int i = numberOfElements - 1; i > 0; i--)
    {
        // Move current root to end
        swap(arrayOfNumbers[0], arrayOfNumbers[i]);
        createHeap(arrayOfNumbers, i, 0);
    }
}

void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
  for (int i = 0; i < numberOfElements; ++i)
  {
    cout << arrayOfNumbers[i] << " ";
  }
  cout << endl;
}

int main(void)
{
  int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
  int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);

  heapSort(arrayOfNumbers, numberOfElements);
  cout<<"The sorted array is: \n";
  printElementsOfArray(arrayOfNumbers, numberOfElements);
}