max_queue 最大値をいち早く返すデータ構造

ちょっとマニアックなデータ構造を紹介

その名もmax queue、使い勝手はほとんどFIFOなqueueと一緒で、enqueue()もdequeue()もO(1)だけどそれに加えて「入ってるデータのうち最大の値」もO(1)の計算量で算出するという代物。
兄弟分で最小の物を返すmin queueや、両方の機能を備えたmin-max queueもあるけどmax queueが判れば自明なので割愛。

最大の値を覚えておけば良いだけに思えるけど、最大の値がdequeueされてしまった場合にO(n)の時間を掛けて再び探索してたら条件を満たせない。

max-queueでは最大の値を覚えておくため専用のqueue（以後最大値queueと呼ぶ）を内部でもう一本持つ。

この青い線がqueueに入ってるデータ列で高さがデータの大きさを表す、下に書かれている薄い線の入ったデータ列が最大値queue。
こちらの最大値queueでは過去に入れられたデータのうち、一番大きな物から順番に降順にデータを記録し、他は無視している。
薄い線で書かれたデータは最大値queueの側では保持していない。

複雑そうに見えるけど
enqueueする時に「挿入したいデータよりも小さいデータが最大値dequeueの末尾にあったらそれらを消してから入れる」だけ。
dequeueする時に一緒にその値が出ていくなら最大値queueからも同時にdequeueするだけ。
コードで書くと非常に明快。

https://gist.github.com/3847509

#include <list>

template <typename T>
struct max_queue {
    max_queue():queue_(),max_(){}
    void enqueue(const T& n){
        queue_.push_back(n);
        const T& new_item = queue_.back();
        while(!max_.empty() && *max_.back() < new_item){ // 最新の値より小さい末尾を全部消す
            max_.pop_back();
        }
        max_.push_back(&new_item);
    }
    T dequeue(){
        if(queue_.empty()){ throw std::exception(); }
        const T& deleting_item = queue_.front();
        const T ans = queue_.front(); // copy
        if(max_.front() == &deleting_item){ // 一緒に最大値が出ていくなら一緒に消す
            max_.pop_front();
        }
        queue_.pop_front();
        return ans;
    }
    const T& max()const{
        if(max_.empty()){ throw std::exception(); }
        return *max_.front(); // 最大値dequeueの先端を返すだけ。速い。
    }
private:
    std::list<T> queue_; // 普通のqueue
    std::list<const T*> max_;// 最大値queue
};

#include <assert.h>
#include <iostream>
int main(void){
    max_queue<int> q;
    q.enqueue(1); assert(q.max()==1);
    q.enqueue(3); assert(q.max()==3);
    q.enqueue(5); assert(q.max()==5);
    q.enqueue(2); assert(q.max()==5);
    q.enqueue(7); assert(q.max()==7);
    q.enqueue(4); assert(q.max()==7);
    q.enqueue(1); assert(q.max()==7);
    q.enqueue(2); assert(q.max()==7);
    q.enqueue(1); assert(q.max()==7);
    assert(q.dequeue()==1); assert(q.max()==7);
    assert(q.dequeue()==3); assert(q.max()==7);
    assert(q.dequeue()==5); assert(q.max()==7);
    assert(q.dequeue()==2); assert(q.max()==7);
    assert(q.dequeue()==7); assert(q.max()==4);
    assert(q.dequeue()==4); assert(q.max()==2);
    assert(q.dequeue()==1); assert(q.max()==2);
    assert(q.dequeue()==2); assert(q.max()==1);
    assert(q.dequeue()==1);
}

でも使いどころは割と難しいと思う。