数据结构实现 6.2：优先队列_基于最大二叉堆实现（C++版）_c++二叉堆优先队列

1. 概念及基本框架

队列 是一种现实中很常见的数据结构，但有时候队列排序不仅仅依靠入队时间来决定，而是不同的元素有不同的优先级。显然，通过 6.1 中的 最大二叉堆 可以很容易实现 优先队列 。

优先队列 是 队列 的一种，所以有队列的基本特性：
1.队列 有 队头 和 队尾 两端。
2.入队 操作只能从 队尾 进行，出队 操作只能从 队头 进行。
3.先 入队 的先 出队 ，即 先进先出（First In First Out），FIFO 。
还有一个隐含特性，队列可以自行 扩容（缩容），而不需要用户关心，很显然，最大二叉堆已经满足了这个要求。
首先使用一个由 纯虚函数 构成的 抽象类 作为一个队列接口，接口内定义一些队列的基本操作。具体代码如下：

template <class T>
class Queue{
   
public:
	virtual int size() = 0;
	virtual bool isEmpty() = 0;
	virtual void print() = 0;
	//入队操作
	virtual void enqueue(T num) = 0;
	//出队操作
	virtual void dequeue() = 0;
	//获得队首元素
	virtual T front() = 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

下面只需要通过继承 抽象类，并且重写 纯虚函数 ，就可以完成 优先队列 的实现。优先队列类的框架如下：

template <class T>
class PriorityQueue{
   
	...
private:
	MaxHeap<T> heap;
};
1
2
3
4
5
6
7

同样，这里为了避免重复设计就可以兼容更多数据类型，引入了 泛型 ，即 模板 的概念。（模板的关键字是 class 或 typename）
这里的 heap 表示一个 最大二叉堆 ，同样，为了保护数据，变量设置为 private 。
注：这里没有显式的给出构造函数，因为子类中除了最大二叉堆对象之外没有特别需要初始化的东西。编译器会默认先调用 最大二叉堆 类（即父类）的构造函数，再去调用 优先队列 类（即子类）的构造函数。
实现了前面的程序之后，接下来就是一个队列的增、删、查以及一些其他基本操作，接下来利用代码去实现。

2. 基本操作程序实现

2.1 入队操作

template <class T>
class PriorityQueue{
   
public:
	...
	//入队操作
	void enqueue(T num){
   
		heap.add(num);
	}
	...
};
1
2
3
4
5
6
7
8
9
10
11
12

2.2 出队操作

template <class T>
class PriorityQueue{
   
public:
	...
	//出队操作
	void dequeue(){
   
		heap.extractMax();
	}
	...
};
1
2
3
4
5
6
7
8
9
10
11
12

2.3 查找操作

template <class T>
class PriorityQueue{
   
public:
	...
	//获得队首元素
	T front(){
   
		
1
2
3
4
5
6
7
8