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

• View this file on GitHub
• Last update: 2024-11-15 15:44:55+09:00
• Include: #include "lib/data_structure/double_ended_priority_queue.hpp"

Verified with

• test/library_checker/data_structure/double_ended_priority_queue.test.cpp

Code

#pragma once

/**
 * @brief Double Ended Priority Queue
 */

#include <queue>
#include <vector>
#include <cassert>

template <typename T>
struct DoubleEndedPriorityQueue{
    std::priority_queue<T, std::vector<T>, std::greater<T>> min_q, removed_min;
    std::priority_queue<T> max_q, removed_max;
    DoubleEndedPriorityQueue(){ }

    void normalize(){
        while(!removed_min.empty() && min_q.top() == removed_min.top()) {
            removed_min.pop();
            min_q.pop();
        }
        while(!removed_max.empty() && max_q.top() == removed_max.top()) {
            removed_max.pop();
            max_q.pop();
        }
    }

    void push(const T &x){
        min_q.push(x);
        max_q.push(x);
    }

    void pop_min(){
        assert(!min_q.empty());
        normalize();
        removed_max.push(min_q.top());
        min_q.pop();
    }

    void pop_max(){
        assert(!max_q.empty());
        normalize();
        removed_min.push(max_q.top());
        max_q.pop();
    }

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

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

#line 2 "lib/data_structure/double_ended_priority_queue.hpp"

/**
 * @brief Double Ended Priority Queue
 */

#include <queue>
#include <vector>
#include <cassert>

template <typename T>
struct DoubleEndedPriorityQueue{
    std::priority_queue<T, std::vector<T>, std::greater<T>> min_q, removed_min;
    std::priority_queue<T> max_q, removed_max;
    DoubleEndedPriorityQueue(){ }

    void normalize(){
        while(!removed_min.empty() && min_q.top() == removed_min.top()) {
            removed_min.pop();
            min_q.pop();
        }
        while(!removed_max.empty() && max_q.top() == removed_max.top()) {
            removed_max.pop();
            max_q.pop();
        }
    }

    void push(const T &x){
        min_q.push(x);
        max_q.push(x);
    }

    void pop_min(){
        assert(!min_q.empty());
        normalize();
        removed_max.push(min_q.top());
        min_q.pop();
    }

    void pop_max(){
        assert(!max_q.empty());
        normalize();
        removed_min.push(max_q.top());
        max_q.pop();
    }

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

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

Back to top page