structure/heap/erasable-heap.hpp

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "structure/heap/erasable-heap.hpp"

Code

#pragma once

#include <cassert>
#include <queue>

template <typename T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type> >
class erasable_heap {
  std::priority_queue<T, Container, Compare> base, erased;

  void normalize() {
    while (true) {
      if (base.empty()) break;
      if (erased.empty()) break;
      if (base.top() != erased.top()) break;
      base.pop();
      erased.pop();
    }
  }

 public:
  bool empty() const { return base.empty(); }

  const T &top() const {
    assert(!empty());
    return base.top();
  }

  void push(T val) {
    base.push(std::move(val));
    normalize();
  }

  template <class... Args>
  void emplace(Args... args) {
    base.emplace(args...);
    normalize();
  }

  void pop() {
    assert(!empty());
    base.pop();
    normalize();
  }

  void erase(T val) {
    erased.push(std::move(val));
    normalize();
  }
};

#line 2 "structure/heap/erasable-heap.hpp"

#include <cassert>
#include <queue>

template <typename T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type> >
class erasable_heap {
  std::priority_queue<T, Container, Compare> base, erased;

  void normalize() {
    while (true) {
      if (base.empty()) break;
      if (erased.empty()) break;
      if (base.top() != erased.top()) break;
      base.pop();
      erased.pop();
    }
  }

 public:
  bool empty() const { return base.empty(); }

  const T &top() const {
    assert(!empty());
    return base.top();
  }

  void push(T val) {
    base.push(std::move(val));
    normalize();
  }

  template <class... Args>
  void emplace(Args... args) {
    base.emplace(args...);
    normalize();
  }

  void pop() {
    assert(!empty());
    base.pop();
    normalize();
  }

  void erase(T val) {
    erased.push(std::move(val));
    normalize();
  }
};

Back to top page