priority_queue|multiset

c++中STL中，除了bitset、priority_queue(堆，也叫优先队列)以及AVL(平衡树相关)，其他的都可以进行短时间的手撕代码进行实现，本次博客主要是阐述一些讲一下堆与平衡树的基本用法，以及其中区别所在

priority_queue	堆/优先队列

定义：	
    
priority_queue<T>
priority_queue<int> 大根堆
priority_queue<int, vector<int>, less<int> > 大根堆
priority_queue<int, vector<int>, greater<int> > 小根堆
priority_queue <struct T>
    
基本函数：

push(x)：加入一个元素，可以是数 or 结构体

pop()：弹出堆顶

top()：堆顶的元素

size()：堆的大小

empty()：是否为空（空即为 1）

关于结构体的比较：

struct type
{
	int x,y;
	bool friend operator < (type left, type right) 
    {
        return left.x < right.x;
    }
};
结构体的赋值可以为{a,b,...}或名称{a,b,...}

multiset vs set
    multiset 可以有重复元素，故一般情况下，（除解决重复元素的集合类问题）都用 multiset
	multiset 也进行自实现排序。

定义：

multiset<T>
multiset<int> 从小到大
multiset<int, less<int> > less<int>表示数字大的优先级大
multiset<int, greater<int> > greater<int>表示数字小的优先级大
multiset<struct T>
    
迭代器：

multiset<定义和对应的 set 一致> ::iterator，其作用是遍历 set/特别指向某一个元素

基本函数：

insert(x)：加入一个元素，可以是数/结构体

erase(x)：当x为数或结构体，即为删掉所有的x；当x 为迭代器，那么只会删掉迭代器对应的元素

begin()：返回关键值最小的元素指针，指针x对应的值为 *x，如果是结构体则为（*x）.a

end()：返回关键值最大的元素指针的后一位（最大的是end()--）

size(), empty()：同优先队列

lower_bound(x)：第一个大于等于 x 的元素指针

upper_bound(x)：第一个大于 x 的元素指针

multiset<T> st
st.insert(1);
st.insert(2);
st.insert(3);
st.insert(4);
st.insert(5);
cout<<*st.lower_bound(3)<<" " <<*st.upper_bound(3)<<endl;    //>= >
cout<<*--st.lower_bound(3)<<" "<<*--st.upper_bound(3)<<endl; //< <=
//3 4
//2 3
遍历：
可以通过迭代器的移动来遍历（头为 begin()，尾为--end()，最大能走到 end()）

st.insert(1);
st.insert(2);
st.insert(3);
auto a = st.begin();
while (a != st.end())
{
    cout<< *a <<" ";
    ++a;
	cout<<endl;
}
//1 2 3区别
//multiset可以遍历、前驱、后继、删除；
//而priority_queue的比较机制和set/sort相反
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>

#define fo(a, b, c) for (a = b; a <= c; a++)
#define fd(a, b, c) for (a = b; a >= c; a--)

using namespace std;

struct type
{
	int x,y;
	bool friend operator < (type left, type right) 
    {
        return left.x < right.x;//此处不能重载大于号，在数学上来说重载小于号的作用更好
    }
};

multiset<type> a;
priority_queue<type> b;
type c[3];

int main()
{
    a.insert({3,3});
    a.insert({2,2});
    a.insert({1,1});
    b.push({1,1});
    b.push({2,2});
    b.push({3,3});
    c[0] = {3,3};
    c[1] = {2,2};
    c[2] = {1,1};
    sort(c, c + 3);
    cout << (*a.begin()).x <<" " << b.top().x << " " << c[0].x << endl;
    //1 3 1
}

可以发现，priority_queue得到的结果和multiset/sort 刚好相反.

实际上multiset与sort的最终的状态满足 a1 < a2 < a3 < … < an（ < 可重载）

而priority_queue应该是当一个元素x满足 f(a[x]) < x 时交换，实质上维护的是大根堆

优先队列 ⇔ 排序后为先大后小