#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>

using namespace std;

class Node {
private:
    int key;

public:
    Node(int key) {
        this->key = key;
    }

    int getKey() {
        return this->key;
    }
};

class Heap {
private:
    vector<Node*> nodes;
    int size;

    int compareTo(Node* a, Node* b) {
        return a->getKey() - b->getKey();
    }

    void upHeap(int index) {
        if ((index - 1) / 2 >= 0 && compareTo(nodes[index], nodes[(index - 1) / 2]) < 0) {
            Node* t = nodes[index];
            nodes[index] = nodes[(index - 1) / 2];
            nodes[(index - 1) / 2] = t;

            upHeap((index - 1) / 2);
        }
    }

    void downHeap(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        Node* t;
        if (right < size) {
            if (compareTo(nodes[index], nodes[left]) < 0 && compareTo(nodes[index], nodes[right]) < 0) {
                return;
            }

            if (compareTo(nodes[left], nodes[right]) < 0) {
                t = nodes[left];
                nodes[left] = nodes[index];
                nodes[index] = t;

                downHeap(left);
            } else {
                t = nodes[right];
                nodes[right] = nodes[index];
                nodes[index] = t;

                downHeap(right);
            }
        } else if (left < size) {
            if (compareTo(nodes[index], nodes[left]) < 0) {
                return;
            }

            t = nodes[index];
            nodes[index] = nodes[left];
            nodes[left] = t;

            downHeap(left);
        }
    }

public:

    Heap() {
        this->size = 0;
    }

    Heap(vector<int>& nodes) {
        this->size = 0;

        for (auto & it : nodes) {
            this->add(it);
        }
    }

    ~Heap() {
        for (auto & it : nodes) {
            delete it;
        }
    }

    void add(int val) {
        nodes.push_back(new Node(val));
        size++;

        upHeap(size - 1);
    }

    Node* remove() {
        if (size < 1) {
            cout << "Kopiec pusty!" << endl << endl;
            return NULL;
        }

        Node* t = nodes[0];
        nodes[0] = nodes[size - 1];
        nodes[size - 1] = t;

        Node* root = nodes[size - 1];
        nodes.pop_back();
        size--;

        downHeap(0);

        return root;
    }

    void clean() {
        while (size > 0) {
            remove();
        }
    }

    void display() {
        cout << "Rozmiar kopca: " << size << endl;
        for (auto & it : nodes) {
            cout << it->getKey() << endl;
        }

        cout << endl;
    }
};

int main() {

    srand((unsigned) time(NULL));

    const int MAX_ORDER = 7;
    Heap* heap = new Heap();
    for ( int o = 1; o <= MAX_ORDER ; o++)
    {
        const int n = pow (10 , o);

        clock_t t1 = clock ();
        for ( int i = 0; i < n; i++) {
            int randomValue = rand() % n;
            heap->add(randomValue);
        }
        clock_t t2 = clock ();

        cout << "Czas wykonania (dodawanie): " << (double) (t2 - t1) / CLOCKS_PER_SEC << endl << endl;

        t1 = clock();
        for ( int i = 0; i < n; i++) {
            Node* polled = heap->remove();
            cout << polled->getKey() << endl;
            delete polled ;
        }
        t2 = clock();
        cout << endl;

        cout << "Czas wykonania (usuwanie): " << (double) (t2 - t1) / CLOCKS_PER_SEC << endl << endl;
    }

    delete heap;
}