-
java优先队列的入队函数_Java内置的优先队列PriorityQueue
2021-03-08 04:25:45PriorityQueue是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);
-
优先队列优先队列优先队列优先队列
2018-09-26 20:35:33最大优先队列,无论入队顺序,当前最大的元素优先出队。 最小优先队列,无论入队顺序,当前最小的元素优先出队。 比如有一个最大优先队列,它的最大元素是8,那么虽然元素8并不是队首元素,但出队的时候仍然让...优先队列优先队列优先队列
那么,优先队列又是什么样子呢?
优先队列不再遵循先入先出的原则,而是分为两种情况:
最大优先队列,无论入队顺序,当前最大的元素优先出队。
最小优先队列,无论入队顺序,当前最小的元素优先出队。
比如有一个最大优先队列,它的最大元素是8,那么虽然元素8并不是队首元素,但出队的时候仍然让元素8首先出队:
-
优先队列的实现
2019-12-04 21:11:461.“上浮”操作(用于优先队列入队) 2.“下沉”操作(用于优先队列出队) 3.完整代码 一、什么是优先队列? 我们知道队列的特点是先进先出(FIFO),第一个进队列的元素最先出队,而优先队列的出队顺序,不是按...在我的上一篇文章(二叉堆的节点插入、删除以及构建过程)中,介绍了二叉堆,包括最大堆和最小堆,优先队列正是基于二叉堆来实现的。
目录
一、什么是优先队列?
我们知道队列的特点是先进先出(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 -
hdu 5195 BC#35 拓扑排序 优先队列 重复入队的想法 十字链表
2015-03-30 21:10:40思路 用优先队列维护入度小于等于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:371.简介 队列的特点是:先进先...二叉堆是实现优先队列得基础,二叉堆中堆节点的“上浮”和“下沉”的时间复杂度都是O(logn),所以优先队列的入队和出队操作的时间复杂度都是O(logn) 2.代码实现 import java.util.A -
优先队列 01 基于最大堆的优先队列
2019-02-12 14:49:00从队列的角度来看,优先队列,入队的时候,优先级高的元素会插队,插到它该排的位置,整个队列从队首到队尾,优先级一次降低; public class PriorityQueue<E extends Comparable<E>> implements Queue... -
图解优先队列
2020-04-20 11:12:15最大优先队列:无论入队顺序如何,都是当前最大的元素优先出队。 最小优先队列:无论入队顺序如何都是当前最小的元素优先出队。 存储结构: 最大优先队列可以用二叉堆的大顶堆实现 最小优先队列可以用二叉... -
优先队列(3道优先队列问题)
2017-04-14 19:30:55优先队列是一种十分强大的数据结构,它保持了一种动态的有序性,对于不断改变有入队的操作,而又需要某种最大或最小的操作的问题是再合适不过了,通常优先队列的实现是由最小堆或者最大堆完成的,并通过堆排序保持... -
堆实现优先队列
2019-10-26 21:12:51在前面讲了用链队实现优先队列,其思想是插入元素时按普通队列入队,在删除元素(出队)时按优先队列的性质删除.那么就还有一种方式,即插入元素时按优先队列的方式插入,删除时按普通顺序队列的方式删除.那就是用堆实现... -
索引优先队列
2020-11-10 16:25:16优先队列2. 索引优先队列的用途3. 算法原理4. 代码实现 1. 优先队列 对于普通队列,我们只能遵循先进先出的原则访问,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高... -
java 优先队列
2018-11-16 20:13:53队列的基本准则就是先进先出,优先队列有两种,一种就是最大优先队列,就是不管入队元素,先让队列里的最大值先出队,另一种就是最小优先队列,就是不管入队元素,先让队列里的最小的元素先出队,运用二叉堆的方法... -
java优先队列_算法基础02-栈、队列、优先队列、双端队列、哈希表、映射、集合...
2020-11-29 08:06:43同时支持先进先出和后进先出优先队列的本质是入队与队列相同,出队按优先级顺序出队,底层实现可能是堆、平衡二叉树等栈、队列、双端队列的的插入删除时间复杂度都是O(1),搜索和遍历时间复杂度都是O(n)优先队列的... -
堆&优先队列
2019-05-23 12:54:02最大优先队列,无论入队顺序,当前最大的元素优先出队。 最小优先队列,无论入队顺序,当前最小的元素优先出队。 3例题 215. 数组中的第K个最大元素 3.1优先队列或红黑树(TreeSet)解法 public int ... -
hdu1285 优先队列+拓扑排序 或者 (动态开点实现优先队列+拓扑排序)
2020-04-14 21:57:20这题主要是优先队列的用法,我们需要让已经入队的元素按照小的来出队,这时候普通的队列已经不满足了,我们需要用到优先队列,由于优先队列的实现其实就是堆的建立,入队出队操作的时间复杂度是log,比一般队列慢很... -
JS 优先队列
2018-04-04 18:03:34一般情况下从队列中删除的元素,一定是率先...优先队列中元素的添加和移除是基于优先级的,从优先队列中删除元素时,需要考虑优先权的限制。优先队列具有最高级先出(First In Largest Out)的行为特征。 例如:医院...