Double-Ended Priority Queue
(data_structure/double_ended_priority_queue.hpp)

• View this file on GitHub
• Last update: 2024-03-08 13:39:50+09:00
• Include: #include "data_structure/double_ended_priority_queue.hpp"

説明

constructor

double_ended_priority_queue() = default // (1)

double_ended_priority_queue(InputIterator first, InputIterator last) // (2)

• (1) デフォルトコンストラクタ
• (2) $[first, last)$ の要素で構築する $O(N)$

empty()

空であるかを判定する。 $O(1)$

size()

要素数を所得する。 $O(1)$

push(T x)

x を追加。 $O(\log{N})$

emplace(Args &&…args)

要素型 T のコンストラクタ引数をとり、直接構築で要素を追加する。 $O(\log{N})$

pop_min()

最小値を取り除く。 $O(\log{N})$

pop_max()

最大値を取り除く。 $O(\log{N})$

get_min()

最小値を所得する。 $O(1)$

get_max()

最大値を所得する。 $O(1)$

Depends on

• Removable Priority Queue (data_structure/removable_priority_queue.hpp)

Verified with

• test/data_structure/Double-Ended_Priority_Queue.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

#include "../data_structure/removable_priority_queue.hpp"

namespace ebi {

template <class T> struct double_ended_priority_queue {
  public:
    double_ended_priority_queue() = default;

    template <class InputIterator>
    double_ended_priority_queue(InputIterator first, InputIterator last) {
        min = removable_priority_queue<T, std::vector<T>, std::greater<T>>(
            first, last);
        max = removable_priority_queue<T>(first, last);
    }

    bool empty() const {
        return min.empty() && max.empty();
    }

    int size() const {
        assert(min.size() == max.size());
        return min.size();
    }

    void push(T x) {
        min.push(x);
        max.push(x);
    }

    template <class... Args> void emplace(Args &&...args) {
        min.emplace(std::forward<Args>(args)...);
        max.emplace(std::forward<Args>(args)...);
        return;
    }

    void pop_min() {
        T x = min.top();
        min.pop();
        max.remove(x);
    }

    void pop_max() {
        T x = max.top();
        max.pop();
        min.remove(x);
    }

    T get_min() {
        assert(!min.empty());
        return min.top();
    }

    T get_max() {
        assert(!max.empty());
        return max.top();
    }

  private:
    removable_priority_queue<T, std::vector<T>, std::greater<T>> min;
    removable_priority_queue<T> max;
};

}  // namespace ebi

#line 2 "data_structure/double_ended_priority_queue.hpp"

#include <cassert>
#include <vector>

#line 2 "data_structure/removable_priority_queue.hpp"

#include <functional>
#include <queue>
#line 6 "data_structure/removable_priority_queue.hpp"

/*
    reference: https://twitter.com/maspy_stars/status/1436690222465486848
    verify: https://atcoder.jp/contests/abc218/submissions/25800862
*/

namespace ebi {

template <class T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
struct removable_priority_queue {
  private:
    void update() {
        while (!rm_que.empty() && que.top() == rm_que.top()) {
            que.pop();
            rm_que.pop();
        }
        return;
    }

  public:
    removable_priority_queue() = default;

    template <class InputIterator>
    removable_priority_queue(InputIterator first, InputIterator last) {
        que = std::priority_queue<T, Container, Compare>(first, last);
    }

    bool empty() const {
        return (size() == 0);
    }

    int size() const {
        return int(que.size() - rm_que.size());
    }

    T top() {
        assert(!empty());
        update();
        return que.top();
    }

    void pop() {
        assert(!empty());
        update();
        que.pop();
        return;
    }

    void push(const T &x) {
        que.push(x);
        return;
    }

    template <class... Args> void emplace(Args &&...args) {
        que.emplace(std::forward<Args>(args)...);
        return;
    }

    void remove(const T &x) {
        rm_que.push(x);
        assert(que.size() >= rm_que.size());
        return;
    }

    template <class... Args> void emplace_remove(Args &&...args) {
        rm_que.emplace(std::forward<Args>(args)...);
        assert(que.size() >= rm_que.size());
        return;
    }

  private:
    std::priority_queue<T, Container, Compare> que, rm_que;
};

}  // namespace ebi
#line 7 "data_structure/double_ended_priority_queue.hpp"

namespace ebi {

template <class T> struct double_ended_priority_queue {
  public:
    double_ended_priority_queue() = default;

    template <class InputIterator>
    double_ended_priority_queue(InputIterator first, InputIterator last) {
        min = removable_priority_queue<T, std::vector<T>, std::greater<T>>(
            first, last);
        max = removable_priority_queue<T>(first, last);
    }

    bool empty() const {
        return min.empty() && max.empty();
    }

    int size() const {
        assert(min.size() == max.size());
        return min.size();
    }

    void push(T x) {
        min.push(x);
        max.push(x);
    }

    template <class... Args> void emplace(Args &&...args) {
        min.emplace(std::forward<Args>(args)...);
        max.emplace(std::forward<Args>(args)...);
        return;
    }

    void pop_min() {
        T x = min.top();
        min.pop();
        max.remove(x);
    }

    void pop_max() {
        T x = max.top();
        max.pop();
        min.remove(x);
    }

    T get_min() {
        assert(!min.empty());
        return min.top();
    }

    T get_max() {
        assert(!max.empty());
        return max.top();
    }

  private:
    removable_priority_queue<T, std::vector<T>, std::greater<T>> min;
    removable_priority_queue<T> max;
};

}  // namespace ebi

Back to top page