leetcode周赛记录_leetcode周赛做题统计网站

243

优先级队列 struct排序

STL中堆的实现——priority_queue

注意 priority queue stack 都不是容器，而是容器适配器，所以其中是没有迭代器的，STL中的算法不适用于容器适配器

在默认情况下，优先级队列使用的是vector容器，less模版
优先级队列总是保证优先级最高的元素在队首，在使用less模版时，使用的是小于号
op(x,y)认为x小于y时，数学上x也小于y 因此 数学上最大的放在队首

//创建一个空的priority_queue容器适配器
    std::priority_queue<int>values;
    //使用 push() 成员函数向适配器中添加元素
    values.push(3);//{3}
    values.push(1);//{3,1}
    values.push(4);//{4,1,3}
    values.push(2);//{4,2,3,1}
    //遍历整个容器适配器
    while (!values.empty())
    {
   
        //输出第一个元素并移除。
        std::cout << values.top()<<" ";
        values.pop();//移除队头元素的同时，将剩余元素中优先级最大的移至队头
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

通过函数对象自定义排序规则

/* 函数对象类模板 */
template <typename T>
class cmp
{
   
    public:
    bool operator()(T a, T b)
    {
   
        return a > b;
    }
};
	/* 自定义优先级队列使用的底层容器与排序规则 */
    priority_queue<int, vector<int>, cmp<int>> test;
    test.push(1);
    test.push(2);
    test.push(3);
    while(!test.empty())
    {
   
        cout << test.top() << endl;
        test.pop();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

头文件中的 std::less 和 std::greater ，各自底层实现采用的都是函数对象类模版的方式。

template <typename<
1