#include <iostream>

void addToMaxHeap(int* heap, int& heapSize, int arraySize, int value);
int parent(int childIndex);
int left(int parentIndex);
int right(int parentIndex);
void swap(int& a, int& b);
void displayHeap(int* heap, int heapSize);
void sort(int* heap, int& heapSize);

int main()
{
    const auto arraySize = 10;
    const auto values = new int[arraySize] { 1, 3, 56, 6, 7, 12, 7, 65, 22, 18 };
    const auto heap = new int[arraySize];
    auto heapSize = 0;

    for (auto i = 0; i < arraySize; i++)
        addToMaxHeap(heap, heapSize, arraySize, values[i]);

    displayHeap(heap, heapSize);
    std::cout << std::endl;

    sort(heap, heapSize);
    displayHeap(heap, arraySize);

    getchar();
    return EXIT_SUCCESS;
}

void sort(int* heap, int& heapSize)
{
    while (heapSize > 0)
    {
        swap(heap[heapSize - 1], heap[0]);
        heapSize--;

        auto current = 0;
        auto biggest = heap[left(current)] > heap[right(current)] ? left(current) : right(current);

        while (heap[biggest] > heap[current] && biggest < heapSize)
        {
            swap(heap[biggest], heap[current]);
            current = biggest;
            biggest = heap[left(current)] > heap[right(current)] ? left(current) : right(current);
        }
    }
}

void addToMaxHeap(int* heap, int& heapSize, const int arraySize, const int value)
{
    if (heapSize >= arraySize)
        return;

    heap[heapSize] = value;
    auto current = heapSize;
    heapSize++;

    while (current > 0 && heap[current] > heap[parent(current)])
    {
        swap(heap[current], heap[parent(current)]);
        current = parent(current);
    }
}

int parent(const int childIndex)
{
    return childIndex % 2 ? (childIndex - 1) / 2 : childIndex / 2;
}

int left(const int parentIndex)
{
    return parentIndex * 2 + 1;
}

int right(const int parentIndex)
{
    return parentIndex * 2 + 2;
}

void swap(int& a, int& b)
{
    const auto c = a;
    a = b;
    b = c;
}

void displayHeap(int* heap, const int heapSize)
{
    for (auto i = 0; i < heapSize; i++)
        std::cout << heap[i] << " ";
}