基本概念

        既然是通过二叉堆来实现一个优先队列，那么我们需要先知道什么是二叉堆，实际上，二叉堆的本质就是一个数组，只是我们从逻辑上将这个数组看作一颗完全二叉树，而这颗完全二叉树就是二叉堆。

        二叉堆又分为小根堆和大根堆，要判断一个二叉堆是哪种类型，首先要找到第一个非叶子节点的数组索引，假如数组的末尾元素索引是n，那么第一个非叶子节点的数组索引就是(n-1)/2。

        比如如图所示二叉堆的第一个非叶子节点的元素就是5。

        由此引出大根堆的性质，当i>=0并且i<=(n-1)/2时，如果arr[i]>arr[2*i+1]并且arr[i]>arr[2*i+2]，也就是当前数组的节点i的元素的值，不仅大于其右孩子的值也大于其左孩子的值，对于整个数组的i都是如此，那么这个二叉堆就是一个大根堆。

        相应的如果arr[i]

堆的操作

        如果要向一个二叉堆中增加元素，也就是入堆操作，那么添加的元素只能在数组的末尾，然后判断元素是否需要进行上浮操作，调整元素的位置，使其满足这个二叉堆的性质。

        如果要删除一个二叉堆中的元素，也就是出堆操作，那么删除的元素只能是堆顶元素也就是数组的0号位元素，并且用数组的末尾元素将数组的0号位元素进行覆盖，并判断覆盖后的0号位元素是否需要进行下沉操作。

        对于二叉堆来说，由于它本身的二叉树结构，因此入堆和出堆的时间复杂度都是log(n)。

代码实现

        要通过二叉堆实现一个优先队列，实际上就是将二叉堆的下沉和上浮操作进行封装，达到一个入队列和出队列的操作。

class PriorityQueue { 	using Cmp = std::function; private: 	int size;//队列中的元素个数 	int cap;//队列占用的总空间大小(以元素大小为单位) 	int* que;//指向动态数组的指针 	Cmp cmp; public: 	PriorityQueue(int cap = 20, Cmp cmp = std::greater()) :size(0), cmp(cmp), cap(cap) 	{ 		que = new int[cap]; 	} 	PriorityQueue(Cmp cmp) :cmp(cmp),size(0), cap(20) 	{ 		que = new int[cap]; 	} 	~PriorityQueue() 	{ 		delete[]que; 		que = nullptr; 	} 	//入堆函数 	void push(int val) 	{ 		if (size == cap) 		{ 			int* p = new int[cap * 2]; 			memcpy(p, que, cap*sizeof(int)); 			delete[]que; 			que = p; 			cap *= 2; 		} 		if (size == 0) 		{ 			que[size] = val; 		} 		else 		{ 			siftup(size, val); 		} 		size++; 	} 	//出堆函数 	void pop() 	{ 		if (size == 0)throw "the queue is empty"; 		size--; 		if (size > 0) 		{ 			siftdown(0, que[size]); 		} 	} 	//上浮函数 	void siftup(int i,int val) 	{ 		//最多上浮到首元素 		while (i > 0) 		{ 			int father = (i - 1) / 2;//从孩子的索引推出父亲的索引 			if (cmp(val,que[father])) 			{ 				que[i]=que[father]; 				i = father; 			} 			else 			{ 				break; 			} 		} 		que[i] = val; 	} 	//下沉函数 	void siftdown(int i, int val) 	{ 		//不能下沉超过第一个非叶子节点 		while (i <= (size - 1 - 1) / 2)//(n-1)/2 		{ 			int child = 2 * i + 1; 			//找到两个孩子中，满足条件的孩子 			if (child + 1 < size && cmp(que[child + 1], que[child])) 			{ 				child = child + 1; 			} 			if (cmp(que[child], val)) 			{ 				que[i] = que[child]; 				i = child; 			} 			else 			{ 				break; 			} 		} 		que[i] = val; 	} 	bool empty() const 	{ 		return size == 0; 	} 	int getsize()const 	{ 		return size; 	} 	int top()const 	{ 		if (size == 0) 			throw "que is empty"; 		return que[0]; 	} };

这里我使用了一个函数对象作为构造函数的传入参数，这样用户就可以自己定义优先队列的构造机制，可以是小根堆也可以是大根堆，用户只需要自己定义传入的函数对象就可以了，默认的话就是大根堆。

测试代码

int main() { 	PriorityQueue que; 	srand(time(NULL)); 	for (int i = 0; i < 10; i++) 	{ 		que.push(i+1); 	} 	while(!que.empty()) 	{ 		std::cout << que.top()<< " "; 		que.pop(); 	} 	return 0; }

从输出结果也可以发现，大根堆每次出堆的都是整个数组中的最大元素。