#include <iostream>
#include <vector>
#include <fstream>


class Heap {
public:
    int pop();
    void push(int);
    void print() const;
    bool empty() const;

    static std::vector<int>& sort(std::vector<int>&);
    Heap(std::vector<int> v);
private:
    std::vector<int> data;

    void bubble_up(int index);
    void bubble_down(int index);
    void dump(std::ofstream&, int) const;
};

std::vector<int>& Heap::sort(std::vector<int>& v){
    Heap h(v);
    for(auto& i: v) i = h.pop();
    return v;
}

Heap::Heap(std::vector<int> v): data(std::move(v)){
    for(int i = data.size()/2; i >= 0; i--){
        bubble_down(i);
    }
}

void Heap::bubble_up(int index){
    for(int i = index; i > 1; i /= 2){//neindexuje od 1, jen nulty prvek nema kam vysplhat
        if(data.at(i-1) < data.at(i/2-1)) std::swap(data[i-1], data[(i/2)-1]);
        else break;
    }   
}

void Heap::bubble_down(int index){
    while(true){
        if(data.size() <= 2*index+1) break;
        int small_child_i;
        if(data.size() > 2*index+2 && data.at(2*index+2) < data.at(2*index+1))
            small_child_i = 2*index+2;
        else small_child_i = 2*index+1;

        if(data.at(index) > data.at(small_child_i)){
            std::swap(data[index], data[small_child_i]);
            index = small_child_i;
        }else break;
    }
}

void Heap::push(int h){
    data.push_back(h);
    bubble_up(data.size());
}

int Heap::pop(){
    if (empty()) throw std::out_of_range("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
    std::swap(data[0], data[data.size()-1]);
    int garbage = data.back();
    data.pop_back();
    bubble_down(0);
    return garbage;
}

bool Heap::empty() const{
    return data.empty();
}


void Heap::dump(std::ofstream& ofs, int idx) const {
    if (data.size() - 1 > 2 * idx) {
        ofs << data[idx] << " -> " << data[idx * 2 + 1] << '\n';
        dump(ofs, idx * 2 + 1);
    }
    if (data.size() - 1 > 2 * idx + 1) {
        ofs << data[idx] << " -> " << data[idx * 2 + 1 + 1] << '\n';
        dump(ofs, idx * 2 + 1 + 1);
    }
}

void Heap::print() const {
    std::ofstream ofs;
    ofs.open("viz.dot");
    ofs << "digraph Tree {\n";
    dump(ofs, 0);
    ofs << "}";

    ofs.close();
    system("cat viz.dot | dot -Tx11");
}



int main() {

    Heap h({9, 7, 6, 5, 4, 3, 2, 1, 0, -3, 8});
    std::vector<int> v = {4,6,2,8,0,56,3,4,7,8,2,3,45,5,4,2,432,69,42};
    Heap::sort(v);
    for(auto& i: v){
        std::cout<<i<<", ";
    }
    // for (auto i : v) {
    //     h.push(i);
        h.print();
    // }
    // while (!h.empty()){
    //     int i = h.pop();
    //     h.print();
    // }
    // int aaaaaaaaaaaaaaa = h.pop();
}