double_ended_heap.hpp¶
维护可重复元素集合，并同时快速取得或删除最小值和最大值；适合双端优先队列题型。
Complexity: Time: \(O(\log m)\) amortized per operation; a min/max/empty call may clean up many deferred deletions. Space: \(O(m)\), where \(m\) counts stored entries including deferred deletions, not just live elements.
AC 记录：double_ended_priority_queue。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log m) amortized per operation; a min/max/empty call
/// may clean up many deferred deletions. Space: O(m), where m counts stored
/// entries including deferred deletions, not just live elements.
#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <vector>
namespace noya {
/// @brief Priority queue supporting lazy deletion of arbitrary elements.
template <class T, class C> struct removable_heap {
std::priority_queue<T, std::vector<T>, C> p, q;
void push(T x) { p.emplace(x); }
// Remove one occurrence of an element that is currently present.
void pop(T x) {
if (!p.empty() && p.top() == x)
p.pop();
else
q.emplace(x);
}
bool empty() {
while (!p.empty() && !q.empty() && p.top() == q.top()) {
p.pop();
q.pop();
}
return p.empty();
}
T top() {
while (!p.empty() && !q.empty() && p.top() == q.top()) {
p.pop();
q.pop();
}
assert(!p.empty());
return p.top();
}
};
/// @brief Double-ended heap supporting push, lazy pop, get_min, and get_max.
template <class T> struct double_ended_heap {
removable_heap<T, std::greater<>> mn;
removable_heap<T, std::less<>> mx;
void push(T x) {
mn.push(x);
mx.push(x);
}
void pop(T x) {
mn.pop(x);
mx.pop(x);
}
T get_min() { return mn.top(); }
T get_max() { return mx.top(); }
};
} // namespace noya
// NOYA_DOUBLE_ENDED_HEAP_HPP
#ifndef NOYA_DOUBLE_ENDED_HEAP_HPP
#define NOYA_DOUBLE_ENDED_HEAP_HPP 1
/// @complexity Time: O(log m) amortized per operation; a min/max/empty call
/// may clean up many deferred deletions. Space: O(m), where m counts stored
/// entries including deferred deletions, not just live elements.
#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <vector>
namespace noya {
/// @brief Priority queue supporting lazy deletion of arbitrary elements.
template <class T, class C> struct removable_heap {
std::priority_queue<T, std::vector<T>, C> p, q;
void push(T x) { p.emplace(x); }
// Remove one occurrence of an element that is currently present.
void pop(T x) {
if (!p.empty() && p.top() == x)
p.pop();
else
q.emplace(x);
}
bool empty() {
while (!p.empty() && !q.empty() && p.top() == q.top()) {
p.pop();
q.pop();
}
return p.empty();
}
T top() {
while (!p.empty() && !q.empty() && p.top() == q.top()) {
p.pop();
q.pop();
}
assert(!p.empty());
return p.top();
}
};
/// @brief Double-ended heap supporting push, lazy pop, get_min, and get_max.
template <class T> struct double_ended_heap {
removable_heap<T, std::greater<>> mn;
removable_heap<T, std::less<>> mx;
void push(T x) {
mn.push(x);
mx.push(x);
}
void pop(T x) {
mn.pop(x);
mx.pop(x);
}
T get_min() { return mn.top(); }
T get_max() { return mx.top(); }
};
} // namespace noya
#endif // NOYA_DOUBLE_ENDED_HEAP_HPP
/// @complexity Time: O(log m) amortized per operation; a min/max/empty call
/// may clean up many deferred deletions. Space: O(m), where m counts stored
/// entries including deferred deletions, not just live elements.
#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <vector>
namespace noya {
/// @brief Priority queue supporting lazy deletion of arbitrary elements.
template <class T, class C> struct removable_heap {
std::priority_queue<T, std::vector<T>, C> p, q;
void push(T x) { p.emplace(x); }
// Remove one occurrence of an element that is currently present.
void pop(T x) {
if (!p.empty() && p.top() == x)
p.pop();
else
q.emplace(x);
}
bool empty() {
while (!p.empty() && !q.empty() && p.top() == q.top()) {
p.pop();
q.pop();
}
return p.empty();
}
T top() {
while (!p.empty() && !q.empty() && p.top() == q.top()) {
p.pop();
q.pop();
}
assert(!p.empty());
return p.top();
}
};
/// @brief Double-ended heap supporting push, lazy pop, get_min, and get_max.
template <class T> struct double_ended_heap {
removable_heap<T, std::greater<>> mn;
removable_heap<T, std::less<>> mx;
void push(T x) {
mn.push(x);
mx.push(x);
}
void pop(T x) {
mn.pop(x);
mx.pop(x);
}
T get_min() { return mn.top(); }
T get_max() { return mx.top(); }
};
} // namespace noya
// NOYA_DOUBLE_ENDED_HEAP_HPP