#include <iostream>
#include <atomic>
using uint = unsigned int;

struct Heap
{
    uint arr[100];
    uint size;
    Heap()
        : size(0)
    {

    }
};

void downHeap(Heap &heap, int i)
{
    uint left = 2 * i + 1;
    uint right = 2 * i + 2;
    uint largest = i;

    if ((left < heap.size) && (heap.arr[left] > heap.arr[i]))
        largest = left;
    else
        largest = i;

    if ((right < heap.size) && (heap.arr[right] > heap.arr[i]))
        largest = right;

    if (i != largest)
    {
        std::swap(heap.arr[largest], heap.arr[i]);
        downHeap(heap, largest);
    }
}

void upHeap(Heap &heap, int i)
{
    if (i > 0)
    {
        uint parent = (i - 1) / 2;
        if(heap.arr[i] > heap.arr[parent])
        {
            std::swap(heap.arr[parent], heap.arr[i]);
            upHeap(heap, parent);
        }
    }
}

void make_heap(Heap &heap)
{
    for (uint i = heap.size / 2; i > 0; --i)
        downHeap(heap, i);
}

void insert(Heap &heap, int value)
{
    heap.arr[heap.size] = value;
    upHeap(heap, heap.size++);
}

void show(Heap &heap)
{
    for (uint i = 0; i < heap.size; ++i)
        std::cout << "Ojciec: " << heap.arr[i]
        << " Dzeici: " << heap.arr[i * 2 + 1] << " " << heap.arr[i * 2 + 2] << std::endl;
}

uint extract_max(Heap &heap)
{
    if (heap.size < 1)
        std::cout << "BRAK DANYCH!" << std::endl;
    else
    {
        int max = heap.arr[0];
        std::swap(heap.arr[0], heap.arr[heap.size-- - 1]);
        downHeap(heap, 0);

        return max;
    }

}

void heapSort(Heap &heap)
{
    make_heap(heap);
    int n = heap.size;
    for (uint i = n / 2; i > 0; --i)
    {
        std::swap(heap.arr[i], heap.arr[1]);
        --n;
        downHeap(heap, 0);
    }
}