优先队列/堆

优先队列又名二叉堆，是特殊的二叉树，二叉堆有两种，大根堆和小根堆。

两种操作：

1. 插入某一个元素：先将该元素插在数的最底部，其结构始终满足完全二叉树，然后根据完全二叉树的结构去调整插入元素的位置

2. 删除堆顶元素：先将最后一个元素插到堆顶，然后根据完全二叉树的性质将堆顶元素不断调整。

   priority_queue 默认是大根堆

   小根堆：priority_queue <int,vector,greater > q;

   大根堆：priority_queue <int,vector,less >q;

手动实现：以《合并果子》为例

using namespace std;
int q[10010],cnt = 0;
void push(int x)
{
    cnt++;
    q[cnt] = x;
    int i = cnt,j = i / 2;
    while(j != 0 && q[j] > q[i])
    {
        swap(q[i],q[j]);
        i = j;
        j /= 2;
    }
}
int top()
{
    return q[1];
}
void pop()
{
    q[1] = q[cnt];
    cnt--;
    int i = 1,j = i * 2;
    if(j + 1 <= cnt && q[j + 1] < q[j]) j += 1;
    while(j <= cnt && q[i] > q[j])
    {
        swap(q[i],q[j]);
        i = j;
        j = i * 2;
        if(j + 1 <= cnt && q[j + 1] < q[j]) j += 1;
    }
}
int a[10010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        push(a[i]);
    }
    int ans = 0;
    for(int i = 1;i <= n - 1;i++)
    {
        int a = top();
        pop();
        int b = top();
        pop();
        ans += a + b;
        push(a + b);
    }
    cout << ans << endl;
    return 0;
}

map/set

内部是用二叉搜索/排序树来实现的(平衡二叉树,复杂度是o（logn）

排序的顺序是：左子树 <= 根 <= 右子树

该树的中序遍历就是这个序列本身。、

map也可以看做自定义下标的数组。

map<string,int> mp,第一个参数叫做键值。

set只存在键值，所以可以理解为集合。