/*
    Copyright 2016 Marek "p2004a" Rusinowski
    Binary Heap
*/
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
#include <random>

using namespace std;

template<class T, class Compare=less<T>>
class BinHeap {
    Compare comp;
    vector<T> a;

    size_t left_child(size_t i) { return 2 * i + 1; }
    size_t right_child(size_t i) { return 2 * i + 2; }
    size_t parent(size_t i) { return (i - 1) / 2; }

    void heapify(size_t i) {
        size_t highest = i;
        if (left_child(i) < a.size() && comp(a[left_child(i)], a[highest])) {
            highest = left_child(i);
        }       
        if (right_child(i) < a.size() && comp(a[right_child(i)], a[highest])) {
            highest = right_child(i);
        }
        if (highest != i) {
            swap(a[i], a[highest]);
            heapify(highest);
        }
    }

  public:
    explicit BinHeap(const Compare& comp_ = Compare()) : comp(comp_) {}

    template<class InputIt>
    BinHeap(InputIt first, InputIt last, const Compare& comp_ = Compare()) : comp(comp_), a(first, last) {
        for (size_t i = a.size() / 2; i > 0; --i) {
            heapify(i);
        }
        heapify(0);
    }

    const T& top() const {
        return a[0];
    }

    T pop() {
        T elem = move(a[0]);
        a[0] = move(a.back());
        a.pop_back();
        heapify(0);
        return elem;
    }

    void insert(T&& value) {
        a.emplace_back(move(value));
        for (size_t i = a.size() - 1; i > 0 && comp(a[i], a[parent(i)]); i = parent(i)) {
            swap(a[i], a[parent(i)]);
        }
    }

    size_t size() const {
        return a.size();
    }

    bool empty() const {
        return a.empty();
    }
};

struct NonCopyable {
    int value;
    NonCopyable(int value_ = 0) : value(value_) {}
    NonCopyable(const NonCopyable&) = delete;
    NonCopyable& operator = (const NonCopyable&) = delete;

    NonCopyable(NonCopyable&&) = default;
    NonCopyable& operator = (NonCopyable&&) = default;
};

bool operator<(const NonCopyable& lhs, const NonCopyable& rhs) {
    return lhs.value < rhs.value;
}

int main() {
    random_device rd;
    default_random_engine gen(rd());
    uniform_int_distribution<> dis(0, 100);

    vector<int> init;
    for (int i = 0; i < 30; ++i) {
        init.emplace_back(dis(gen));
    }
    BinHeap<int, greater<int>> heap1(init.begin(), init.end());
    while (!heap1.empty()) {
        printf("%d ", heap1.pop());
    }
    printf("\n");

    BinHeap<NonCopyable> heap2;
    for (int i = 0; i < 30; ++i) {
        heap2.insert(NonCopyable(dis(gen)));
    }
    while (!heap2.empty()) {
        printf("%d ", heap2.pop().value);
    }
    printf("\n");
    return 0;
}