本文由 李奕樊 原创, 请勿抄袭

讨论链接

前言

优先队列( $priority\_queue$ )，它是 $STL$ 所提供的一个非常有效的容器。

作为队列的一个延伸，优先队列包含在头文件 < $queue$ >中

$C ++$ 中的优先队列是 $STL$ 中的派生容器，它仅考虑最高优先级元素。队列遵循 先进先出 $(FIFO, First Input First Output)$ 策略，而优先队列根据优先级弹出元素，即，优先级最高的元素首先弹出。

它在某些方面类似于普通队列，但在以下方面有所不同：

• 在优先队列中，队列中的每个元素都与某个优先级相关联，但是优先级在队列数据结构中不存在。
• 优先队列中具有最高优先级的元素将被首先删除，而队列遵循​FIFO（先进先出）​策略，这意味着先插入的元素将被首先删除。
• 如果存在多个具有相同优先级的元素，则将考虑该元素在队列中的顺序。

优先队列的成员函数

具体用法：

$bool$ $empty()$ 返回值为 $true$，说明队列为空；

$int$ $size()$ 返回优先队列中元素的数量；

$void$ $pop()$ 删除队列顶部的元素，也即根节点

$int$ $top()$ 返回队列中的顶部元素，但不删除该元素；

$void$ $push(int num)$ 将元素 $num$插入到队列之中；

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N = 1e7 + 10; // 最多1e7 

class Priority_queue{
	public:
    //公共的行为或属性
 	bool Push(int num) { // 添加元素
        if (len >= N) { // 超过数组最大值 
        	return false; // 加入未成功 
		}
	    Queue[len].num = num; // 添加元素
	    Queue[len].idx = len; // 设置 idx
	    len++; // 长度 + 1
	 	Update(); // 实时排序
	 	return true; // 加入成功 
	}
	
	bool Pop() { // 删除元素
		if (len <= 0) { // 当队列没有元素时, 返回false
			return false;
		}
		len --; // 长度 - 1 无需删数
		Update(); // 实时排序
	}
	
	int Size(){ // 长度函数
		return len; // 返回长度
	}
	
	int Top() { // 返回队列顶端的函数
		return Queue[len-1].num;
	}
	
	bool Empty() { // 判空函数
		return len == 0; // 判断队列是否为空
	}
	
    private:
    //私密的行为或属性
    
	int len = 0; // 长度, 从 0 开始
	
    struct Data{ // 结构体
    	int num; // 数
    	int idx; // 序号, 从 1 开始
	};
	
	Data Queue[N]; // 数组
    void Data_sort(int Start, int finish) { // 实时排序
    	if (Start >= finish) { // 没有元素时终止
    		return ;
		}
		if (finish == 1) { // 只有 1 个元素时终止
			return ;
		}
    	for (int i = Start; i <= finish; i++) { // 冒泡排序
    		bool flag = true;
			for (int j = finish - 1; j > i; j--) {
    			if (Queue[j].num < Queue[j-1].num) {
    				int temp = Queue[j-1].num;
    				Queue[j-1].num = Queue[j].num;
    				Queue[j].num = temp;
    				// printf("q[%d]: %d q[%d]:%d b: %dlen:%d \n", j,Queue[j].num, j - 1, Quere[j-1].num, Start,finish);
					flag = false;
				}
			}
			if (flag) {
				break;
			}
		}
	}
    
    void Update(){ // 实时处理
        Data_sort(0, len);
	}
};

Priority_queue q;

int main() {
	int n;
	scanf("%d", &n);
	
	for (int i = 0; i < n; i ++) {
		int num;
		scanf("%d", &num);
		q.Push(num);
	}
	
	while (!q.Empty()) {
        printf("%d ", q.Top());
        q.Pop();
	}
	
	return 0;
}

后言(蒟蒻的吐槽)

1. 在 $devcpp$ 运行时会有一个消不掉的 $Warning$ , 心态崩溃
2. 不知为何 $N$ 定义在 $Class$里会报错
3. 还有居然用 $vector$ 也会报错

欢迎大佬们来吐槽提提意见