両端ヒープ

概要

最大値・最小値の両方の取り出しに対応したヒープです．std::set でも同じことができますが定数倍で勝ります．下の実装方法は hogloid さん考案？

使い方

std::priority_queue とほぼ同じです．

計算量

ならし $O(\log n)$

実装

template <class T>
class HogloidHeap {
private:
    std::size_t sz;
    std::priority_queue<T> g, gd;
    std::priority_queue<T, std::vector<T>, std::greater<T> > l, ld;
    void flush_min() {
        while (!ld.empty() && l.top() == ld.top()) {
            l.pop();
            ld.pop();
        }
    }
    void flush_max() {
        while (!gd.empty() && g.top() == gd.top()) {
            g.pop();
            gd.pop();
        }
    }

public:
    HogloidHeap() : sz(0) {}
    bool empty() const { return size() == 0; }
    std::size_t size() const { return sz; }
    const T &min() {
        flush_min();
        return l.top();
    }
    const T &max() {
        flush_max();
        return g.top();
    }
    void push(const T &v) {
        l.push(v);
        g.push(v);
        ++sz;
    }
    template <class... Args>
    void emplace(Args &&... args) {
        l.emplace(std::forward<Args>(args)...);
        g.emplace(std::forward<Args>(args)...);
        ++sz;
    }
    void pop_min() {
        flush_min();
        gd.emplace(l.top());
        l.pop();
        --sz;
    }
    void pop_max() {
        flush_max();
        ld.emplace(g.top());
        g.pop();
        --sz;
    }
};

検証

自前で検証．

参考文系

Double-Ended Priority - 週刊 spaghetti_source