PriorityQueue是Java内置的优先队列，每次取出来的元素是最小的。PriorityQueue可以做到自动扩容。PriorityQueue中的对象必须是可比较的。
例如，最简单的情况，在PriorityQueue中保存整数：
PriorityQueue priInt = new PriorityQueue<>();
然后在其中依次添加五个整数(注意，在PriorityQueue中添加对象，可以调用add，也可以调用offer。)
priInt.add(1);
priInt.add(3);
priInt.add(4);
priInt.add(5);
priInt.add(2);
然后通过poll函数所取出来的值就是从小到大排列好的1，2，3，4，5
int n = priInt.poll(); //n is 1
n = priInt.poll(); //n is 2
n = priInt.poll(); //n is 3
n = priInt.poll(); //n is 4
n = priInt.poll(); //n is 5
PriorityQueue中还可以放置自定义对象。由于PriorityQueue中的对象必须是可比较的，所以必须为自定义对象定义比较规则。
例如，对于自定义类
classMyClass {intn1;intn2;public MyClass(int n1, intn2) {this.n1 =n1;this.n2 =n2;
}
}
具体做法有3种
1、MyClass实现接口Comparable，在override的函数compareTo中定义比较规则
static class MyClass implements Comparable{intn1;intn2;public MyClass(int n1, intn2) {this.n1 =n1;this.n2 =n2;
}
@Overridepublic intcompareTo(MyClass o) {return this.n2 -o.n2;
}
}
然后，PriorityQueue上就不用做任何额外的操作了，直接定义即可
PriorityQueue priMyClass = new PriorityQueue<>();
2、在PriorityQueue的参数中，通过Comparator接口定义比较规则
PriorityQueue priMyClass = new PriorityQueue<>(new Comparator() {public intcompare(MyClass o1, MyClass o2) {return o1.n2 -o2.n2;
}
}
);
3、在PriorityQueue的参数中，通过lambda表达式定义比较规则。写起来最省事
PriorityQueue priMyClass = new PriorityQueue<>((MyClass o1, MyClass o2) -> o1.n2 - o2.n2);

优先队列优先队列优先队列

那么，优先队列又是什么样子呢？

 

优先队列不再遵循先入先出的原则，而是分为两种情况：

 

最大优先队列，无论入队顺序，当前最大的元素优先出队。

最小优先队列，无论入队顺序，当前最小的元素优先出队。

 

比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：

在我的上一篇文章（二叉堆的节点插入、删除以及构建过程）中，介绍了二叉堆，包括最大堆和最小堆，优先队列正是基于二叉堆来实现的。

目录

一、什么是优先队列？

二、优先队列的实现

1.“上浮”操作（用于优先队列入队）

2.“下沉”操作（用于优先队列出队）

3.完整代码

一、什么是优先队列？

我们知道队列的特点是先进先出（FIFO），第一个进队列的元素最先出队，而优先队列的出队顺序，不是按照入队顺序来排序的。

在一个最大优先队列中，无论入队顺序如何，都是当前最大的元素优先出队。
	
在一个最小优先队列中，无论入队顺序如何，都是当前最小的元素优先出队。
当然，我们可以用线性的数据结构来实现最大优先队列和最小优先队列，但是算法的时间复杂度会比较高O(n)。

二、优先队列的实现

若我们采用最大堆来实现最大优先队列，栈顶元素就是最大元素，那么每次入队时，都将元素插在二叉堆最后一个位置，然后进行“上浮”操作（此时是将较大的值往上移）；在出队时，即是删除堆顶节点，然后将最后一个节点替换到堆顶位置，再进行该节点的“下沉”操作（此时是将较小的值往下移，同样理解为大值上移）。

因为上浮操作和下沉操作的时间复杂度是O(logn)，所以优先队列的入队和出队的时间复杂度也是O(logn)。


先说明一点：构建最大优先队列或者最小优先队列的区别，只是在入队和出队时，“上浮”和“下沉”操作中，变换判断的符号即可。 


1.“上浮”操作（用于优先队列入队）

在最大优先队列（对应于最大堆，父节点值大于左右孩子节点）入队时，因为插入的位置在二叉堆的最后位置，若该元素为较大的元素，则需要将该节点进行“上浮”。

“上浮”操作（构建最大堆）的思路：

用childIndex来记录插入的节点位置，用temp值记录需要“上浮”的节点值，将childIndex的值与父节点的值进行比较，若孩子节点的值大于父节点，则进行“上浮”操作：单向赋值（无需实际交换两个值），将父节点值赋给孩子节点，然后将孩子节点指针指向父节点，并重新计算父节点指针。若一直上浮到根节点，此时childIndex=0，那么直接将temp值赋值给根节点，因此循环判断的条件中要加上childIndex > 0.具体的实现为：

//实现一个最大堆
    public void upAdjust(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while(childIndex > 0 && temp > array[parentIndex]){//若后一个大于号改为小于号，则是最小堆
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

2.“下沉”操作（用于优先队列出队）

在最大优先队列（对应于最大堆）出队时，我们移除堆顶节点，同时将最后一个节点替换堆顶节点，此时需要进行“下沉”操作。

“下沉”操作（构建最大堆）的思路：

用childIndex来记录左右孩子中较大的那个，然后将父节点与该孩子节点进行比较，若孩子节点值大于父节点，则进行“下沉”操作，同样是单向赋值，循环的条件为childIndex < size(数组长度），当父节点值大于等于孩子节点时，退出循环。具体实现为：

public void downAdjust(){
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while(childIndex < size){
            if(childIndex + 1 < size && array[childIndex+1] > array[childIndex]){//若构建最小堆将后一个大于号改为小于号
                childIndex++;
            }
            if(array[parentIndex] >= array[childIndex])//若构建最小堆将大于等于改为小于等于
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;//此处一定是parentIndex，因为childIndex可能已经超尺寸了
    }

3.完整代码

下面以最大优先队列的入队和出队为例，给出完整的代码实现。

import java.util.Arrays;

public class PriorityQueue {
    private int[] array;
    private int size;
    public PriorityQueue(){
        array = new int[32];
    }

    //入队（最大优先队列）
    public void enQueue(int key){
        if(size >= array.length)
            resize();
        array[size++] = key;
        upAdjust();//实现最小优先队列，这里将upAjust()改为upAdjust1()即可
    }

    //出队（最大优先队列）
    public int deQueue() throws Exception {
        if(size <= 0)
            throw new Exception("队列为空，不能出队！");
        int head = array[0];
        array[0] = array[--size];
        downAdjust();//实现最小优先队列，这里将downAjust()改为downAdjust1()即可
        return head;
    }

    //实现一个最大堆
    public void upAdjust(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while(childIndex > 0 && temp > array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    //实现一个最小堆，只需要将判断条件中的大于号改为小于号即可
    public void upAdjust1(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while(childIndex > 0 && temp < array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    //实现一个最大堆
    public void downAdjust(){
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while(childIndex < size){
            if(childIndex + 1 < size && array[childIndex+1] > array[childIndex]){//最大堆中左右孩子节点取较大的那个进行移动
                childIndex++;
            }
            if(array[parentIndex] >= array[childIndex])
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;//此处一定是parentIndex，因为childIndex可能已经超尺寸了
    }

    //实现一个最小堆
    public void downAdjust1(){
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while(childIndex < size){
            if(childIndex + 1 < size && array[childIndex+1] < array[childIndex]){//最小堆中左右孩子节点取较小的那个进行移动
                childIndex++;
            }
            if(temp <= array[childIndex])
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;//此处一定是parentIndex，因为childIndex可能已经超尺寸了
    }

    public void resize(){
        int newLength = array.length * 2;
        this.array = Arrays.copyOf(this.array,newLength);//剩余长度用0补齐
    }

    public static void main(String[] args) throws Exception{
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        System.out.println("出队元素： "+priorityQueue.deQueue());
        System.out.println("出队元素： "+priorityQueue.deQueue());
    }
}


运行的结果为：


出队元素： 10

出队元素： 7

题意 求可以删除K条边的DAG图的最大字典序的拓扑序列
思路 用优先队列维护入度小于等于K的点（注意入队后，不改变K），BFS，每次看堆顶元素i的入度是否小于等于当前的K，是则K减入度，删去到i的边，继续从i搜索，否则出队，继续看堆顶元素，重复上述步骤。继续搜到的点入度如果小于等于当前K则入队，注意维护是否入队的数组，不要重复入队~


注意点：（1）拓扑排序删边，不用真删，只要维护入度数组减一就行！！！
   （2）就算是要真删，也可以用个is_del数组来表示这边是否真的删去，没必要从链表里删掉！
   （3）我这题为了删去所有到一个点的边还写了个十字链表。。。真是二了。。。
                             不过可以当做今后的十字链表模板
   （4）注意维护in_q这个数组，防止队中有重复元素
//#include <iostream>
#include <stdio.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <map>
using namespace std;
#define I64_MAX 9223372036854775807 
typedef long long ll;
const double pi=acos (-1.0);
const double eps=1e-8 ;
//const ll INF=(I64_MAX)/2;
//#pragma comment(linker, "/STACK:102400000,102400000")
const int inf=0x3f3f3f3f ;
#define maxx(a) memset(a, 0x3f, sizeof(a))
#define zero(a) memset(a, 0, sizeof(a))
#define FILL(a,b) memset(a, b, sizeof(a))
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define srep(i,n) for(i = 1;i <= n;i ++)
#define snuke(c,itr) for( __typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define MP make_pair
#define fi first
#define se second
typedef pair <int, int> PII;
typedef pair <ll, ll> PX;
typedef pair<int,ll> PIL;
#define maxn 100005

int n,m;

int ru[maxn];
//int chu[maxn];
priority_queue<int> q;
queue<int> q_print;
int in_q[maxn];
struct Edge{
	int u,v,next,pre,rnext,rpre;
	void set(int uu=0,int vv=0,int nextt=-1,int rnextt=-1,int pree=-1,int rpree=-1)
	{
		this->u = uu;
		this->v = vv;
		this->next = nextt;
		this->pre = pree;
		this->rnext = rnextt;
		this->rpre = rpree;
	}
}edge[maxn];

int g[maxn];
int rg[maxn];

void init()
{
	memset(g,-1,sizeof(g));
	memset(rg,-1,sizeof(rg));
//	memset(chu,0,sizeof(chu));
	memset(ru,0,sizeof(ru));
	memset(in_q,0,sizeof(in_q));
	while(q.size()>0)
		q.pop();
	while(q_print.size()>0)
		q_print.pop();
}

void addEdge()
{
	for(int i=0;i<m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		edge[i].set(u,v,g[u],rg[v]);
		g[u] = i;
		rg[v] = i;
		if(edge[i].next != -1)
			edge[edge[i].next].pre = i;
		if(edge[i].rnext != -1)
			edge[edge[i].rnext].rpre = i;
		ru[v]++;
	}
}

void del(int e)
{
	if(edge[e].pre == -1)
	{
		g[edge[e].u] = edge[e].next;
	}
	else
	{
		edge[edge[e].pre].next =  edge[e].next;
	}
	if(edge[e].rpre == -1)
	{
		rg[edge[e].v] = edge[e].rnext;
	}
	else
	{
		edge[edge[e].rpre].rnext =  edge[e].rnext;
	}
	if(edge[e].next != -1)
	{
		edge[edge[e].next].pre = edge[e].pre;
	}
	if(edge[e].rnext != -1)
	{
		edge[edge[e].rnext].rpre = edge[e].rpre;
	}
	//return edge[e].next;
}

void delAll(int i)
{
	for(int e=rg[i];e!=-1;e=edge[e].rnext)
	{
		del(e);
	}
}

int main ()
{
	#ifdef LOCAL
    // freopen("E:\\input.txt" ,"r", stdin);
     // freopen ("E:\\out.txt","w",stdout);
	#endif
	int i,j;
	int K;
	while(scanf("%d%d%d",&n,&m,&K)==3)
	{
		init();
		addEdge();
		for(i=n;i>=1;i--)
		{
			if(ru[i] <= K)
			{
				q.push(i);
				in_q[i] = 1;
			}
		}
		while(q.size() > 0)
		{
			int tmp;
			while(1)
			{
				tmp = q.top();
				q.pop();
				in_q[tmp] = 0;
				if(ru[tmp] <= K)
				{
					delAll(tmp);
					K -= ru[tmp];
					ru[tmp] = 0;
					break;
				}
			}
			q_print.push(tmp);
			for(int e=g[tmp];e!=-1;e=edge[e].next)
			{
				ru[edge[e].v]--;
				if(ru[edge[e].v] <= K && in_q[edge[e].v]==0)
				{
					q.push(edge[e].v);
					in_q[edge[e].v] = 1;
				}
				del(e);
			}
		}
		while(q_print.size()>1)
		{
			int tmp = q_print.front();
			printf("%d ",tmp);
			q_print.pop();
		}
		if(q_print.size() == 1)
		{
			int tmp = q_print.front();
			printf("%d\n",tmp);
			q_print.pop();
		}
	}

	return 0;
}