heap

.cpp

#include <iostream>
#include <vector>
#include <string>
#include <utility>

template <class T, class Predicate>
class Heap {
public:
    void Heapify(size_t position) {
        size_t left_pos = Left(position);
        size_t right_pos = Right(position);
        size_t root_place = position;
        if (left_pos < heap_.size() && pred_(heap_[left_pos], heap_[root_place]))
            root_place = left_pos;
        if (right_pos < heap_.size() && pred_(heap_[right_pos], heap_[root_place]))
            root_place = right_pos;
        if (root_place != position) {
            std::swap(heap_[position], heap_[root_place]);
            Heapify(root_place);
        }
    }

    size_t Parent(size_t ind) {
        return (ind - 1) / 2;
    }

    size_t Left(size_t ind) {
        return (2 * ind + 1);
    }

    size_t Right(size_t ind) {
        return (2 * ind + 2);
    }

    void InsertKey(T new_val) {
        heap_.push_back(new_val);
        size_t countdown = heap_.size() - 1;
        while (countdown != 0 && pred_(heap_[countdown], heap_[Parent(countdown)])) {
            std::swap(heap_[countdown], heap_[Parent(countdown)]);
            countdown = Parent(countdown);
        }
    }

    void UpRootKey(size_t place, T new_val) {
        heap_[place] = new_val;
        while (place != 0 && pred_(heap_[place], heap_[Parent(place)])) {
            std::swap(heap_[place], heap_[Parent(place)]);
            place = Parent(place);
        }
    }

    T ExtractRoot() {
        T root = heap_[0];
        if (heap_.size() == 1) {
            heap_.pop_back();
            return root;
        }
        heap_[0] = heap_[heap_.size() - 1];
        heap_.pop_back();
        Heapify(0);
        return root;
    }

    std::vector<T> Get() {
        return heap_;
    }


    T GetRoot() {
        return heap_[0];
    }

    void DeleteKey(size_t place) {
        UpRootKey(place, heap_[0]);
        ExtractRoot();
    }


private:
    std::vector<T> heap_;
    Predicate pred_;
};