noob题单 优先队列 章——noob109

一开始创建了两个优先序列最大堆和最小堆，卡在7/10怎么也过去，翻题解翻讨论结果要么哈希要么集合，遂放弃，直接找神秘力量

整数n <= 1e5,所有我们可以运用数组标记的方法，直接给他定义四个优先序列，当我们从最小堆中删除一个元素时，我们并不真正从最小堆中删除，而是标记到max_deleted中，然后当最大堆的堆顶元素被标记为已删除（即max_deleted[堆顶元素]为真）时，我们就弹出最大堆直到堆顶元素未被删除。同样，从最大堆中删除时，我们标记min_deleted。

这样我们哈希不需要，集合也不用，但是效率低，有点复杂；

but我觉得对我们理解优先序列很有帮助，直接看注释吧，我写的应该很详细了；

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class double_ended_priority_queue
{
private:
//创建两个主堆

    //最小堆
    priority_queue<int,vector<int>,greater<int>> min_pq;
    //最大堆
    priority_queue<int> max_pq;


//创建两个待删除堆，用来记录需要从对方堆中删除的元素

    //最小堆删除堆
    priority_queue<int,vector<int>,greater<int>> min_to_delete;
    //最大堆删除堆
    priority_queue<int> max_to_delete;


//创建清除函数

    //最小堆清除函数，删除所有标记为待删除的堆顶元素
    void clean_min_pq()
    {
        //两个堆都不为空，同时堆顶元素相同
        while (!min_pq.empty() && !min_to_delete.empty() && min_pq.top() == min_to_delete.top())
        {
            min_pq.pop();
            min_to_delete.pop();
        }
    }

    //最大堆清除函数，删除所有标记为待删除的堆顶元素
    void clean_max_pq()
    {
        //两个堆都不为空，同时堆顶元素相同
        while (!max_pq.empty() && !max_to_delete.empty() && max_pq.top() == max_to_delete.top())
        {
            max_pq.pop();
            max_to_delete.pop();
        }
    }



public:
    //插入函数：将元素同时插入最大堆与最小堆
    void push(int x)
    {
        min_pq.push(x);
        max_pq.push(x);
    }


//创建获取函数

    //最小值获取函数
    int get_min()
    {
        clean_min_pq();  //先清除最小堆待删除元素，防止被获取
        if (min_pq.empty())
        {
            return -1;
        }
        //获取最小堆的顶部元素，即最小值
        int min_num = min_pq.top();
        return min_num;
    }

    //最大值获取函数
    int gei_max()
    {
        clean_max_pq();  //先清除最大堆待删除元素，防止被获取
        if (max_pq.empty()) 
        {
            return -1;
        }
        //获取最大堆顶部元素，即最大值
        int max_num = max_pq.top();
        return max_num;
    }


//创建删除函数

    //最小值删除函数
    void min_pop()
    {
        clean_min_pq();  //依旧先清理
        if (min_pq.empty())
        {
            return;
        }
        //获取要删除的值
        int num_to_delete = min_pq.top();
        //获取后从最小堆中删除
        min_pq.pop();
        //将获取的值加入最大堆待删除列表
        max_to_delete.push(num_to_delete);
    }

    //最大值删除函数
    void max_pop()
    {
        clean_max_pq(); //清理
        if (max_pq.empty())
        {
            return;
        }
        //获取要删除的值
        int num_to_delete = max_pq.top();
        //获取后从最大堆删除
        max_pq.pop();
        //将获取到的值加入最小堆待删除列表
        min_to_delete.push(num_to_delete);
    }


//检查队列是否为空 (这里也可以换成检测最大堆，两个是一样的)
    bool empty()
    {
        //先清理最小堆
        clean_min_pq();  
        //如果最小堆为空，则队列为空
        return min_pq.empty();
    }
};




//主函数部分，这段就很简单了
int main() 
{
    int n = 0;
    cin >> n;
    //创建双端优先序列
    double_ended_priority_queue depq;
    while (n--)
    {
        int op = 0;
        cin >> op;

        //操作1
        if (op == 1)
        {
            int x = 0;
            cin >> x;
            depq.push(x);
        }

        //操作2
        else if(op == 2)
        {
            //这里直接cout get_min()也可以
            int min_num =  depq.get_min();
            cout << min_num << "\n";
        }

        //操作3
        else if (op == 3)
        {
            //同样，可以cout get_max()
            int max_num = depq.gei_max();
            cout << max_num << "\n";
        }

        //操作4
        else if (op == 4)
        {
            //调用最大值删除
            depq.min_pop();
        }

        //操作5
        else if (op == 5)
        {
            //调用最小值删除
            depq.max_pop();
        }

        //处理异常情况
        else 
        {
            return -1;
        }
    }
    return 0;
}

敲红温了其实