优先队列

队列是基于数组或者链表来实现的，是线性的结构；队列的特点是先进先出。

优先队列是一种特殊类型的队列，其中元素被赋予优先级，具有较高优先级的元素先被处理。

在竞赛中经常会遇到优先队列的思想

基本语法

基本语法

定义优先队列

#include <queue>
using namespace std;

// 定义一个最大堆（默认）
priority_queue<int> maxHeap;

// 定义一个最小堆
priority_queue<int, vector<int>, greater<int>> minHeap;

插入元素

maxHeap.push(10);
maxHeap.push(5);

获取栈顶的元素

int topElement = maxHeap.top();

弹出栈顶的元素

maxHeap.pop();

获取队列的大小

int size = maxHeap.size();

判断队列是否为空

bool isEmpty = maxHeap.empty();

优先队列的底层实现通常是通过堆（heap）来实现的，堆可以是最大堆或最小堆，具体取决于比较函数。最大堆是默认的实现，如果想要最小堆，则需要提供比较函数 greater。

题目

[NOIP2004]合并果子
每次都要选选出序列中最小的两个，也可以进行排序，然后每次再添加进来，但是使用优先队列更加的方便，简单。

代码

#include <bits/stdc++.h>
using namespace std;
int n;

int main()
{
  priority_queue<int, vector<int>, greater<int>> queue;
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    int x;
    cin >> x;
    queue.push(x);
  }
  int sum = 0;
  while (queue.size())
  {
    int a = queue.top();
    queue.pop();
    int b = queue.top();
    queue.pop();
    int cost = +b;
    sum = sum + cost;
    queue.push(cost);
  }
  cout << sum;
}