#include <iostream>

//kopce
void addValue(int* heap, int& heapSize, int arraySize, int value);
void bottomUp(int* heap, int& heapSize);
void deleteValue(int* heap, int& heapSize);
void topDown(int* heap, int& heapSize);
int getParentIndex(int childIndex);
void swap(int& a, int& b);
void printHeap(int* heap, int heapSize);
//kopce

int main()
{
    const auto size = 15;
    auto heapSize = 11;
    const auto maxHeap = new int[size] { 15, 12, 11, 10, 11, 8, 5, 3, 7, 2, 9 };

    printHeap(maxHeap, heapSize);

    addValue(maxHeap, heapSize, size, 12);
    bottomUp(maxHeap, heapSize);

    printHeap(maxHeap, heapSize);

    deleteValue(maxHeap, heapSize);
    topDown(maxHeap, heapSize);

    printHeap(maxHeap, heapSize);
    getchar();

    return EXIT_SUCCESS;
}

//kopce
void deleteValue(int* heap, int& heapSize)
{
    swap(heap[0], heap[heapSize - 1]);
    heapSize--;
}

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

    heap[heapSize] = value;
    heapSize++;
}

void bottomUp(int* heap, int& heapSize)
{
    auto currentIndex = heapSize - 1;

    while (currentIndex != 0 && heap[getParentIndex(currentIndex)] < heap[currentIndex])
    {
        swap(heap[getParentIndex(currentIndex)], heap[currentIndex]);
        currentIndex = getParentIndex(currentIndex);
    }
}

void topDown(int* heap, int& heapSize)
{
    auto current = 0;
    auto left = 1;
    auto right = 2;

    swap(heap[0], heap[heapSize - 1]);

    while (current < heapSize && heap[left] > heap[current])
    {
        auto smallest = current;

        if (left < heapSize && heap[left] > heap[current])
            smallest = left;
        if (right < heapSize && heap[right] > heap[smallest])
            smallest = right;

        if (smallest != current)
            swap(heap[current], heap[smallest]);

        current = smallest;
        left = current * 2 + 1;
        right = current * 2 + 2;
    }
}

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

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

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

    std::cout << std::endl;
}
//kopce