前言

提示：本文用C++实现了优先队列：

一、Advantages of priority queues

优先队列（priority queue）可以在 O(1) 时间内获得最大值,并且可以在 O(log n) 时间内取出
Maximum value or insert any value.

二、具体实现方法

优先队列常常用堆（heap）来实现.堆是一个完全二叉树,The value of each node is always greater than or equal to the child
节点的值.实际实现堆时,我们通常用一个数组而不是用指针建立一个树.This is because the heap is exactly two
叉树,所以用数组表示时,位置 i 的节点的父节点位置一定为 i/2,And the position of its two child nodes
must be separately 2i+1 和 2i+2.


以下是堆的实现方法,The two core operations are floatingswim和下沉sink：如果一个节点比父节点大,那
么需要交换这个两个节点;交换后还可能比它新的父节点大,因此需要不断地进行比较和交换操
作,我们称之为上浮;类似地,如果一个节点比父节小,也需要不断地向下进行比较和交换操作,
我们称之为下沉.如果一个节点有两个子节点,我们总是交换最大的子节点.

代码

代码如下：

/* Priority queue to get maximum value quickly 将heap[]The priority queue with the smallest value can be obtained by swapping the greater than or less than signs */
#define N 1000
vector<int> heap;

//上浮
void swim(int pos)
{
    
	while (pos > 0 && heap[pos/2] < heap[pos]) //父小于子
	{
    
		swap(heap[pos/2], heap[pos]); //父子交换
		pos = pos / 2;                //father as son
	}
}

//下沉
void sink(int pos)
{
    
	while (2 * pos + 1 <= N) //Child nodes do not overflow
	{
    
		int i = 2 * pos + 1; //i为pos的左儿子
		// i不越界 左儿子小于右儿子 Then let the right son andpos比较
		if (i < N && heap[i] < heap[i+1]) ++i;
		//如果pos已经大于i的节点值 No need to exchange directlybreak
		if (heap[pos] >= heap[i]) break;
		swap(heap[pos], heap[i]);  //否则就交换
		pos = i; //更新pos为i
	}
}

//插入任意值: Put the number to be inserted in the last digit,然后swim
void push(int k)
{
    
	heap.push_back(k);
	swim(heap.size() - 1);
}

//删除最大值(根): 把最后一个数字挪到开头,然后sink
void pop()
{
    
	heap[0] = heap.back();
	heap.pop_back();
	sink(0);
}

//获得最大值(根)
int top()
{
    
	return heap[0];
}

总结

What is implemented here is a priority queue that can quickly get the maximum value,If the greater than or less than signs in the algorithm are properly interchanged,A priority queue that quickly obtains the minimum value can be implemented,当然,There are already existing ones in the librarypriority_queue供我们使用
C++ priority_queue(STL priority_queue)用法详解