leftist_heap.hpp¶
Meldable leftist heap with O(log n) push, pop, and heap merging.
提供可快速合并的优先队列；题目频繁合并两堆元素并取出极值时使用。
Implementation¶
#ifndef NOYA_LEFTIST_HEAP_HPP
#define NOYA_LEFTIST_HEAP_HPP 1
/// @complexity Time: O(log n) push/pop/meld.
/// Space: O(n) nodes and O(log n) stack.
#include <cassert>
#include <functional>
#include <utility>
namespace noya {
/// @brief Meldable leftist heap with O(log n) push, pop, and heap merging.
template <class T, class Compare = std::less<T>> struct leftist_heap {
struct node {
T value;
node *left = nullptr;
node *right = nullptr;
int rank = 1;
};
node *root = nullptr;
Compare compare{};
leftist_heap() = default;
leftist_heap(const leftist_heap &) = delete;
leftist_heap &operator=(const leftist_heap &) = delete;
leftist_heap(leftist_heap &&other) noexcept
: root(std::exchange(other.root, nullptr)),
compare(std::move(other.compare)) {}
leftist_heap &operator=(leftist_heap &&other) noexcept {
if (this != &other) {
clear(root);
root = std::exchange(other.root, nullptr);
compare = std::move(other.compare);
}
return *this;
}
~leftist_heap() { clear(root); }
bool empty() const { return root == nullptr; }
const T &top() const {
assert(root != nullptr);
return root->value;
}
void push(const T &value) { root = meld(root, new node{value}); }
void push(T &&value) { root = meld(root, new node{std::move(value)}); }
void pop() {
assert(root != nullptr);
node *old = root;
root = meld(root->left, root->right);
delete old;
}
void merge(leftist_heap &other) {
if (this != &other) {
root = meld(root, std::exchange(other.root, nullptr));
}
}
private:
int rank(node *current) const {
return current == nullptr ? 0 : current->rank;
}
node *meld(node *first, node *second) {
if (first == nullptr || second == nullptr) {
return first == nullptr ? second : first;
}
if (compare(second->value, first->value)) {
std::swap(first, second);
}
first->right = meld(first->right, second);
if (rank(first->left) < rank(first->right)) {
std::swap(first->left, first->right);
}
first->rank = rank(first->right) + 1;
return first;
}
void clear(node *current) {
if (current != nullptr) {
clear(current->left);
clear(current->right);
delete current;
}
}
};
} // namespace noya
#endif // NOYA_LEFTIST_HEAP_HPP
#include <cassert>
#include <functional>
#include <utility>
/// @complexity Time: O(log n) push/pop/meld.
/// Space: O(n) nodes and O(log n) stack.
namespace noya {
/// @brief Meldable leftist heap with O(log n) push, pop, and heap merging.
template <class T, class Compare = std::less<T>> struct leftist_heap {
struct node {
T value;
node *left = nullptr;
node *right = nullptr;
int rank = 1;
};
node *root = nullptr;
Compare compare{};
leftist_heap() = default;
leftist_heap(const leftist_heap &) = delete;
leftist_heap &operator=(const leftist_heap &) = delete;
leftist_heap(leftist_heap &&other) noexcept
: root(std::exchange(other.root, nullptr)),
compare(std::move(other.compare)) {}
leftist_heap &operator=(leftist_heap &&other) noexcept {
if (this != &other) {
clear(root);
root = std::exchange(other.root, nullptr);
compare = std::move(other.compare);
}
return *this;
}
~leftist_heap() { clear(root); }
bool empty() const { return root == nullptr; }
const T &top() const {
assert(root != nullptr);
return root->value;
}
void push(const T &value) { root = meld(root, new node{value}); }
void push(T &&value) { root = meld(root, new node{std::move(value)}); }
void pop() {
assert(root != nullptr);
node *old = root;
root = meld(root->left, root->right);
delete old;
}
void merge(leftist_heap &other) {
if (this != &other) {
root = meld(root, std::exchange(other.root, nullptr));
}
}
private:
int rank(node *current) const {
return current == nullptr ? 0 : current->rank;
}
node *meld(node *first, node *second) {
if (first == nullptr || second == nullptr) {
return first == nullptr ? second : first;
}
if (compare(second->value, first->value)) {
std::swap(first, second);
}
first->right = meld(first->right, second);
if (rank(first->left) < rank(first->right)) {
std::swap(first->left, first->right);
}
first->rank = rank(first->right) + 1;
return first;
}
void clear(node *current) {
if (current != nullptr) {
clear(current->left);
clear(current->right);
delete current;
}
}
};
} // namespace noya