创建 priority_queue - 初阶（c++）

 优先级队列

普通的队列是⼀种先进先出的数据结构，即元素插⼊在队尾，⽽元素删除在队头。

⽽在优先级队列中，元素被赋予优先级，当插⼊元素时，同样是在队尾，但是会根据优先级进⾏位置 调整，优先级越⾼，调整后的位置越靠近队头；同样的，删除元素也是根据优先级进⾏，优先级最⾼ 的元素（队头）最先被删除。

其实可以认为，优先级队列就是堆实现的⼀个数据结构。

priority_queue 就是 C++ 提供的，已经实现好的优先级队列，底层实现就是⼀个堆结构。

创建 priority_queue

优先级队列的创建结果有很多种，因为需要根据实际需求，可能会创建出来各种各样的堆： 

1. 简单内置类型的⼤根堆或⼩根堆：⽐如存储 int 类型的⼤根堆或⼩根堆； 
2. 存储字符串的⼤根堆或⼩根堆； 
3. 存储⾃定义类型的⼤根堆或⼩根堆：⽐如堆⾥⾯的数据是⼀个结构体。 

• 关于每⼀种创建结果，都需要有与之对应的写法。在初阶阶段，先⽤简单的 int 类型建堆，我们先重点学习priority_queue 的⽤法。 注意： priority_queue 包含在 queue 这个头⽂件中

size / empty 
1. size ：返回元素的个数。 
2. empty ：返回优先级队列是否为空。 
时间复杂度： O(1) 。 
push 
往优先级队列⾥⾯添加⼀个元素。 
时间复杂度：因为底层是⼀个堆结构，所以时间复杂度为 O(log N) 。 
pop 
删除优先级最⾼的元素。 
时间复杂度：因为底层是⼀个堆结构，所以时间复杂度为 O(log N) 。 
top 
获取优先级最⾼的元素。 
时间复杂度： O(1) 。 

代码：

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

int a[10] = { 1, 41, 23, 10, 11, 2, -1, 99, 14, 0 };

int main()
{
	priority_queue<int> heap; //默认是一个大根堆

	for (int i = 0; i < 10; ++i)
	{
		heap.push(a[i]);
	}

	while (heap.size())
	{
		cout << heap.top() << " "; //99 41 23 14 11 10 2 1 0 -1
		heap.pop();
	}

	return 0;
}