#Pragma once #include <iostream> #include <vector> template <typename T, typename Comp = std::less<T>> class

Heap {
public:
Heap() = default;

Heap(const std::vector<T>& vector) : body_(vector) {
Heapify();
}

template <typename ...Args>
void emplace(Args&&... args) {
body_.emplace_back(std::forward<Args>(args)...);
SiftUp(body_.size() - 1);
}

void extract_top() {
std::swap(body_.front(), body_.back());
body_.pop_back();
SiftDown(0);
}

const T& get_top() const { return body_.front(); }

private:
void Heapify() {
for (size_t i = body_.size(); i > 0; --i) {
SiftDown(i - 1);
}
}

void SiftUp(size_t index) {
while (index != 0) {
size_t parent = (index - 1) / 2;
if (compare_(body_[index], body_[parent])) {
std::swap(body_[index], body_[parent]);
index = parent;
} else {
break;
}
}
}

void SiftDown(size_t index) {
while (index != body_.size() - 1) {
size_t left_child_index = index * 2 + 1;
size_t right_child_index = left_child_index + 1;
if (left_child_index >= body_.size()) {
return;
}
size_t min_child_index =
(right_child_index < body_.size() &&
!compare_(body_[left_child_index], body_[right_child_index]))
? right_child_index
: left_child_index;
if (!compare_(body_[index], body_[min_child_index])) {
std::swap(body_[index], body_[min_child_index]);
index = min_child_index;
} else {
return;
}
}
}

std::vector<T> body_;
Comp compare_;
};
Народ, насколько плоха такая реализация кучи по скорости? Можно как-то улучшить скорость?

можно исходники RTOS посмотреть https://freertos.org/a00111.html