目录
前置知识
概述
命名空间
成员变量
创建销毁
数组操作
堆操作
Code
前置知识
在本篇文章之前：你应该先了解堆与堆排序：「数组」堆排序 / 大根堆优化（C++）
概述
优先队列的本质就是堆。
一般的队列执行先入先出逻辑，而优先队列执行最大/小先出逻辑。也就是说，它的出队原则不再是入队时间，而是队内元素的相对大小关系。
堆有两种实现：二叉堆实现和数组实现，其中，数组实现是最常用的，也是效率较高的。C++内置的优先队列就使用了vector动态数组作为底层实现，今天我们也来动手实现一个优先队列。
总的来讲，我们的优先队列就是堆化的动态数组。
命名空间
C++有自己的std命名空间下的priority_queue，为了进行区分，封装一个自己的优先队列命名空间custom_queue。
namespace custom_priority_queue{...
}成员变量
template <typename T>是泛型，作为数据适配器，他的数据单位应该是任意一种类型，此时暂用T表示，至于T为何物将在实例化时以<>告知。
template<typename T, typename CMP = less<T>>则预定义了类型T和比较类对象CMP，CMP默认设为less<T>。（less和greater时C++内置的仿函数类）
实例化CMP时会实现名为compare的对象，内部重载了()运算符作为bool类型函数，当调用compare(a,b)时，会按内部比较规则传回true或false。如我们使用了less<T>作为比较类，那么传入compare会执行{return a<b;}。（同样的，使用greater则执行{return a>b;}）
*注意*：堆比较时总执行父子比较，即compare(父，子)，我们使用less<T>实例化compare则执行{return 父<子;}，返回真值则发生父子交换，则维护了大根堆。
定义class类priority_queue，封装四个成员变量：
T* val; 数组指针
size_t val_size; 记录数组长度
size_t val_capacity; 记录可用空间
CMP compare; 作为仿函数类，维护大小比较规则。
（size_t 是C/C++标准在stddef.h中定义的（这个头文件通常不需要#include），size_t 类型专门用于表示长度，它是无符号整数。）
另有swap函数实现数据交换，略去不表。
template<typename T,typename CMP = less<T>>
class priority_queue {
private:#define father(x) ((x-1)/2)#define lchild(x) (2*x+1)#define rchild(x) (2*x+2)T* val;size_t val_size;size_t val_capacity;CMP compare;void swap(int& a, int& b) {int temp = b;b = a, a = temp;}...
public:...
};创建销毁
默认构造：priority_queue(int num = 1);
接收一个num，num默认是1。为数组开为1个元素的空间。
复制构造：priority_queue(const priority_queue& another);
按字节复制another。
移动构造：priority_queue(priority_queue&& another);
移动构造详见：「数组」实现动态数组的功能 / 手撕数据结构（C++）
复制赋值运算符：priority_queue& operator=(const priority_queue& another);
类似复制构造。
移动赋值运算符：priority_queue& operator=(priority_queue&& another);
类似移动构造。
析构函数：~priority_queue();
释放底层数组。
priority_queue(int num = 1) :val_size(0), val_capacity(num) {val = new T[num];
};
priority_queue(const priority_queue& another) : val_size(another.val_size), val_capacity(another.val_capacity) {//拷贝构造val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);
}
priority_queue(priority_queue&& another) noexcept : val_size(another.val_size), val_capacity(another.val_capacity) {//移动构造val = another.val;another.val = nullptr;
}
~priority_queue() {delete[] val;
}
priority_queue& operator=(const priority_queue& another) {delete[]val;val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;return *this;
}
priority_queue& operator=(priority_queue&& another) {if (this == &another)return *this;delete[]val;val = another.val;val_size = another.val_size;val_capacity = another.val_capacity;another.val = nullptr;return *this;
}数组操作
获取长度：size_t size();
返回array类型的val内部的val_size。
判断为空：bool empty();
返回array类型的val内部的val_size ? false : true。
延长空间：void reserve(const int num);
如果申请的新空间小于val_capacity，无事发生，否则申请更大的空间。
bool empty()const {return val_size ? false : true;
}
size_t size()const {return val_size;
}
void reserve(const int num) {if (num > val_capacity) {T* temp = new T[num];memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_capacity = num;}
}堆操作
堆操作是优先队列操作的核心。
元素入队（压堆）：void push(V&& elem);
数组容量有限则申请更大的空间，随后元素入堆，再上浮到合适位置。
（template<typename V>后接V&&作为万能引用，是为了对传入的参数进行推断，这样这个函数就能同时接受左值引用和右值引用。如果你不想理解它，可以将函数参数直接改为T elem）
元素出队（出堆）：void pop();
断言val_size>1之后移除堆顶，之后令堆的最后一个元素上升到堆顶，再逐层沉底。
访问队头（堆顶）：const T& top();
返回堆顶的常量引用。
template<typename V>
void push(V&& elem) {if (val_capacity - val_size <= 1)reserve(val_capacity * 2);val[val_size] = elem;up(val_size);val_size++;
}
void pop() {assert(val_size > 0);val[0]=val[--val_size];down(0);
}
const T& top()const {assert(val_size > 0);return val[0];
}交换：void swap(int& a, int& b);
执行元素交换。
上浮与下沉：void up(int idx);void down(int idx);
详见：「数组」堆排序 / 大根堆优化（C++）
*注意*：他们应均声明为私有成员。
void swap(int& a, int& b) {int temp = b;b = a, a = temp;
}
void up(int idx) {if (idx && compare(val[father(idx)],val[idx])) {swap(val[father(idx)], val[idx]);up(father(idx));}
}
void down(int idx) {int pos;if (rchild(idx) < val_size)pos = compare(val[lchild(idx)],val[rchild(idx)]) ? rchild(idx) : lchild(idx);else if (lchild(idx) < val_size)pos = lchild(idx);else return;if (compare(val[idx],val[pos])) {swap(val[idx], val[pos]);down(pos);}
}Code
#include <cassert>
#ifndef CUSTOM_PRIORITY_QUEUE
#define CUSTOM_PRIORITY_QUEUE
namespace custom_priority_queue {template<typename T,typename CMP = less<T>>class priority_queue {private:#define father(x) ((x-1)/2)#define lchild(x) (2*x+1)#define rchild(x) (2*x+2)T* val;size_t val_size;size_t val_capacity;CMP compare;void swap(int& a, int& b) {int temp = b;b = a, a = temp;}void up(int idx) {if (idx && compare(val[father(idx)],val[idx])) {swap(val[father(idx)], val[idx]);up(father(idx));}}void down(int idx) {int pos;if (rchild(idx) < val_size)pos = compare(val[lchild(idx)],val[rchild(idx)]) ? rchild(idx) : lchild(idx);else if (lchild(idx) < val_size)pos = lchild(idx);else return;if (compare(val[idx],val[pos])) {swap(val[idx], val[pos]);down(pos);}}public:priority_queue(int num = 1) :val_size(0), val_capacity(num) {val = new T[num];};priority_queue(const priority_queue& another) : val_size(another.val_size), val_capacity(another.val_capacity) {//拷贝构造val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);}priority_queue(priority_queue&& another) noexcept : val_size(another.val_size), val_capacity(another.val_capacity) {//移动构造val = another.val;another.val = nullptr;}priority_queue& operator=(const priority_queue& another) {delete[]val;val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;return *this;}priority_queue& operator=(priority_queue&& another) {if (this == &another)return *this;delete[]val;val = another.val;val_size = another.val_size;val_capacity = another.val_capacity;another.val = nullptr;return *this;}~priority_queue() {delete[] val;}bool empty()const {return val_size ? false : true;}size_t size()const {return val_size;}void reserve(const int num) {if (num > val_capacity) {T* temp = new T[num];memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_capacity = num;}}template<typename V>void push(V&& elem) {if (val_capacity - val_size <= 1)reserve(val_capacity * 2);val[val_size] = elem;up(val_size);val_size++;}void pop() {assert(val_size > 0);val[0]=val[--val_size];down(0);}const T& top()const {assert(val_size > 0);return val[0];}};
}
#endif
