精华内容
下载资源
问答
  • PriorityQueue是Java内置的优先队列,每次取出来的元素是最小的。PriorityQueue可以做到自动扩容。PriorityQueue中的对象必须是可比较的。例如,最简单的情况,在PriorityQueue中保存整数:PriorityQueue priInt = ...

    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,那么虽然元素8并不是队首元素,但出队的时候仍然让元素8首先出队:

    展开全文
  • 优先队列的实现

    2019-12-04 21:11:46
    1.“上浮”操作(用于优先队列入队) 2.“下沉”操作(用于优先队列出队) 3.完整代码 一、什么是优先队列? 我们知道队列的特点是先进先出(FIFO),第一个进队列的元素最先出队,而优先队列的出队顺序,不是按...

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

    目录

    一、什么是优先队列?

    二、优先队列的实现

    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的点(注意入队后,不改变K),BFS,每次看堆顶元素i的入度是否小于等于当前的K,是则K减入度,删去到i的边,继续从i搜索,否则出队,继续看堆顶元素,重复上述步骤。继续搜到的点...

    题意 求可以删除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;
    }


    展开全文
  • 优先队列

    2021-01-30 11:32:37
    1.简介 ​ 队列的特点是:先进先...二叉堆是实现优先队列得基础,二叉堆中堆节点的“上浮”和“下沉”的时间复杂度都是O(logn),所以优先队列入队和出队操作的时间复杂度都是O(logn) 2.代码实现 import java.util.A
  • 从队列的角度来看,优先队列入队的时候,优先级高的元素会插队,插到它该排的位置,整个队列从队首到队尾,优先级一次降低; public class PriorityQueue<E extends Comparable<E>> implements Queue...
  • 图解优先队列

    2020-04-20 11:12:15
    最大优先队列:无论入队顺序如何,都是当前最大的元素优先出队。 最小优先队列:无论入队顺序如何都是当前最小的元素优先出队。 存储结构: 最大优先队列可以用二叉堆的大顶堆实现 最小优先队列可以用二叉...
  • 优先队列是一种十分强大的数据结构,它保持了一种动态的有序性,对于不断改变有入队的操作,而又需要某种最大或最小的操作的问题是再合适不过了,通常优先队列的实现是由最小堆或者最大堆完成的,并通过堆排序保持...
  • 堆实现优先队列

    2019-10-26 21:12:51
    在前面讲了用链队实现优先队列,其思想是插入元素时按普通队列入队,在删除元素(出队)时按优先队列的性质删除.那么就还有一种方式,即插入元素时按优先队列的方式插入,删除时按普通顺序队列的方式删除.那就是用堆实现...
  • 索引优先队列

    2020-11-10 16:25:16
    优先队列2. 索引优先队列的用途3. 算法原理4. 代码实现 1. 优先队列 对于普通队列,我们只能遵循先进先出的原则访问,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高...
  • java 优先队列

    2018-11-16 20:13:53
    队列的基本准则就是先进先出,优先队列有两种,一种就是最大优先队列,就是不管入队元素,先让队列里的最大值先出队,另一种就是最小优先队列,就是不管入队元素,先让队列里的最小的元素先出队,运用二叉堆的方法...
  • 同时支持先进先出和后进先出优先队列的本质是入队与队列相同,出队按优先级顺序出队,底层实现可能是堆、平衡二叉树等栈、队列、双端队列的的插入删除时间复杂度都是O(1),搜索和遍历时间复杂度都是O(n)优先队列的...
  • 堆&优先队列

    2019-05-23 12:54:02
    最大优先队列,无论入队顺序,当前最大的元素优先出队。 最小优先队列,无论入队顺序,当前最小的元素优先出队。 3例题 215. 数组中的第K个最大元素 3.1优先队列或红黑树(TreeSet)解法 public int ...
  • 这题主要是优先队列的用法,我们需要让已经入队的元素按照小的来出队,这时候普通的队列已经不满足了,我们需要用到优先队列,由于优先队列的实现其实就是堆的建立,入队出队操作的时间复杂度是log,比一般队列慢很...
  • JS 优先队列

    2018-04-04 18:03:34
    一般情况下从队列中删除的元素,一定是率先...优先队列中元素的添加和移除是基于优先级的,从优先队列中删除元素时,需要考虑优先权的限制。优先队列具有最高级先出(First In Largest Out)的行为特征。 例如:医院...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,026
精华内容 410
关键字:

优先队列入队