#include <iostream>
#include <vector>

using namespace std;

class Heap
{
    std::vector<int> h;
    std::vector<int> ID_to_HeapIdx;
    int heap_size;
    int curr_ID;

public:
    Heap();
    void siftup(int ID,std::vector<int>& HeapIdx_to_ID);
    void siftdown(int ID,std::vector<int>& HeapIdx_to_ID);
    void add(int vertex,int ID,std::vector<int>& HeapIdx_to_ID);
    void delete_vertex(int ID,std::vector<int>& HeapIdx_to_ID);
    bool isempty();
    void out();
    int* get_root();
};

Heap::Heap()
{
    std::vector<int> h;
    heap_size = 0;
    curr_ID = 0;
    std::vector<int> ID_to_HeapIdx; //по ID находит где лежит элемент в куче
}

int* Heap::get_root()
{
    return &h[0];
}

bool Heap::isempty()
{
    if (heap_size == 0)
        return true;
    return false;
}

void Heap::siftup(int ID, std::vector<int>& HeapIdx_to_ID)
{
    int curr, parent;
    curr = heap_size - 1;
    parent = (curr - 1) ;
    cout << " do while HeapIdx_to_ID:";
    for (int i = 0; i < HeapIdx_to_ID.size(); i++)
        cout << HeapIdx_to_ID[i] << " ";
    cout << endl;

    cout << "do while  ID_to_HeapIdx:";
    for (int i = 0; i < ID_to_HeapIdx.size(); i++)
        cout << ID_to_HeapIdx[i] << " ";
    cout << endl;

    while (parent >= 0 && curr > 0)
    {


        if (h[parent] < h[curr])
        {
            cout << "parent " << parent << " curr " << curr << endl;

            cout << "do \n";
            cout << "h:";
            for (int i = 0; i < heap_size; i++)
                cout << h[i] << " ";
            cout << endl;

            cout << "HeapIdx_to_ID:";
            for (int i = 0; i < HeapIdx_to_ID.size(); i++)
                cout << HeapIdx_to_ID[i] << " ";
            cout << endl;

            cout << "ID_to_HeapIdx:";
            for (int i = 0; i < ID_to_HeapIdx.size(); i++)
                cout << ID_to_HeapIdx[i] << " ";
            cout << endl;

            int buff = h[curr];
            h[curr] = h[parent];
            h[parent] = buff;

            int tmp;

            tmp = HeapIdx_to_ID[parent];
            HeapIdx_to_ID[parent] = HeapIdx_to_ID[curr];
            HeapIdx_to_ID[curr] = tmp;


            tmp = ID_to_HeapIdx[HeapIdx_to_ID[parent]];
            ID_to_HeapIdx[HeapIdx_to_ID[parent]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
            ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;

             cout << "После \n";
            cout << "h:";
            for (int i = 0; i < heap_size; i++)
                cout << h[i] << " ";
            cout << endl;

            cout << "HeapIdx_to_ID:";
            for (int i = 0; i < HeapIdx_to_ID.size(); i++)
                cout << HeapIdx_to_ID[i] << " ";
            cout << endl;

            cout << "ID_to_HeapIdx:";
            for (int i = 0; i < ID_to_HeapIdx.size(); i++)
                cout << ID_to_HeapIdx[i] << " ";
            cout << endl;


        }
        curr = parent;
        parent = (curr - 1) ;
    }

}

void Heap::add(int vertex, int ID, std::vector<int>& HeapIdx_to_ID)
{

    h.push_back(vertex);
    ID_to_HeapIdx.push_back(heap_size);
    HeapIdx_to_ID.push_back(ID);
    heap_size++;
    siftup(ID, HeapIdx_to_ID);
}

void Heap::siftdown(int ID,std::vector<int>& HeapIdx_to_ID)
{
    int parent, max_child;

    int curr = ID_to_HeapIdx[ID];
    int child_l = 2 * curr + 1;
    int child_r = 2 * curr + 2;

             cout << "h:";
            for (int i = 0; i < heap_size; i++)
                cout << h[i] << " ";
            cout << endl;

            cout << "HeapIdx_to_ID:";
            for (int i = 0; i < HeapIdx_to_ID.size(); i++)
                cout << HeapIdx_to_ID[i] << " ";
            cout << endl;

            cout << "ID_to_HeapIdx:";
            for (int i = 0; i < ID_to_HeapIdx.size(); i++)
                cout << ID_to_HeapIdx[i] << " ";
            cout << endl;

    if (h[child_r] < h[child_l])
        max_child = child_l;
    else
        max_child = child_r;

    while (child_l < heap_size)
    {
        if (child_l == heap_size - 1)
            max_child = child_l;
        else if (h[child_r] < h[child_l])
            max_child = child_l;
        else
            max_child = child_r;

        if (h[curr] < h[max_child])
        {

            int buff = h[curr];
            h[curr] = h[max_child];
            h[max_child] = buff;

            int tmp;
            tmp = HeapIdx_to_ID[max_child];
            HeapIdx_to_ID[max_child] = HeapIdx_to_ID[curr];
            HeapIdx_to_ID[curr] = tmp;

            tmp = ID_to_HeapIdx[HeapIdx_to_ID[max_child]];
            ID_to_HeapIdx[HeapIdx_to_ID[max_child]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
            ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;


        }

        curr = max_child;
        child_l = 2 * curr + 1;
        child_r = 2 * curr + 2;
    }
}



void Heap::delete_vertex(int ID, std::vector<int>& HeapIdx_to_ID)
{
    cout << "ID=" << ID << endl;
    int pos = ID_to_HeapIdx[ID];
    cout << "pos = " << pos << endl;


            cout << "h:";
            for (int i = 0; i < heap_size; i++)
                cout << h[i] << " ";
            cout << endl;

            cout << "HeapIdx_to_ID:";
            for (int i = 0; i < HeapIdx_to_ID.size(); i++)
                cout << HeapIdx_to_ID[i] << " ";
            cout << endl;

            cout << "ID_to_HeapIdx:";
            for (int i = 0; i < ID_to_HeapIdx.size(); i++)
                cout << ID_to_HeapIdx[i] << " ";
            cout << endl;

    h[pos] = h[heap_size - 1];

    cout << "h[pos] = " << h[pos] << endl;
    h.pop_back();
    heap_size--;
            cout << "h:";
            for (int i = 0; i < heap_size; i++)
                cout << h[i] << " ";
            cout << endl;
    siftdown(ID, HeapIdx_to_ID);
}

void Heap::out(void)
{

    for (int i = 0; i < heap_size; i++)
    {
        cout << h[i] << " ";
    }
    cout << endl;
}

int main()
{

    /*
        void siftup(int ID,std::vector<int>& HeapIdx_to_ID);
    void siftdown(int ID,std::vector<int>& HeapIdx_to_ID);
    void add(int vertex,int ID,std::vector<int>& HeapIdx_to_ID);
    void delete_vertex(int ID,std::vector<int>& HeapIdx_to_ID);
    bool isempty();
    void out();
    int* get_root();
    */
    int ID = -1;
    std::vector<int> HeapIdx_to_ID;
    Heap heap;

    //ID++;
    cout << "--------" << endl;
    ID++;
    heap.add(1,ID,HeapIdx_to_ID);
    cout << "heap: ";
    heap.out();
    cout << HeapIdx_to_ID.size() << endl;
    cout << "--------" << endl;
    ID++;
    heap.add(3,ID,HeapIdx_to_ID);
    cout << "heap: ";
    heap.out();
    cout << HeapIdx_to_ID.size() << endl;
    cout << "--------" << endl;
    ID++;
    heap.add(2,ID,HeapIdx_to_ID);
    cout << "heap: ";
    heap.out();
    cout << "--------" << endl;
    cout << "de \n";
    heap.delete_vertex(1,HeapIdx_to_ID);
    heap.out();

    return 0;
}