double_ended_heap.hpp¶

SECTIONData Structure INCLUDEnoya/double_ended_heap.hpp

Priority queue supporting lazy deletion of arbitrary elements.

Verified by double_ended_priority_queue.

维护可重复元素集合，并同时快速取得或删除最小值和最大值；适合双端优先队列题型。

Implementation¶

SourceExpanded

#ifndef NOYA_DOUBLE_ENDED_HEAP_HPP
#define NOYA_DOUBLE_ENDED_HEAP_HPP 1

/// @complexity Time: O(log n) amortized update/pop and O(1) min/max access.
/// Space: O(n), including lazy-deletion entries.

#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); }
  void pop(T x) { 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<>> min_heap;
  removable_heap<T, std::less<>> max_heap;

  void push(T x) {
    min_heap.push(x);
    max_heap.push(x);
  }
  void pop(T x) {
    min_heap.pop(x);
    max_heap.pop(x);
  }

  T get_min() { return min_heap.top(); }
  T get_max() { return max_heap.top(); }
};
} // namespace noya

#endif // NOYA_DOUBLE_ENDED_HEAP_HPP

#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <vector>

/// @complexity Time: O(log n) amortized update/pop and O(1) min/max access.
/// Space: O(n), including lazy-deletion entries.

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); }
  void pop(T x) { 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<>> min_heap;
  removable_heap<T, std::less<>> max_heap;

  void push(T x) {
    min_heap.push(x);
    max_heap.push(x);
  }
  void pop(T x) {
    min_heap.pop(x);
    max_heap.pop(x);
  }

  T get_min() { return min_heap.top(); }
  T get_max() { return max_heap.top(); }
};
} // namespace noya