Java实现--优先级队列
程序员文章站
2022-05-04 15:15:06
...
《Java数据结构和算法》-->像栈和队列一样,优先级队列也经常用作程序员的编程工具。
很多情况下需要访问具有最小关键字的项或者是最大关键字的项,,具有最高或最小的关键字具有最高的优先级。我们就可以采用优先级队列。这里使用的是简单的数组来实现优先级队列,这种实现方法插入比较慢,但是它比较简单,适用于数据量比较小的并且不是特别在意插入速度的情况。有一种比数组要快的,就是使用堆来建立优先级队列。这篇博文说的是按关键字小的有较高的优先级。
这优先级队列没有上一篇博文(循环队列)中的front、rear,我们在构造这个优先级队列的时候已经把他们排序好了。我们remove的时候永远都是从上层把最小关键字的元素丢出去,队尾,只要这个优先级队列不为空,就一直指向QueueArray[0]。
思考Inesrt方法的时候,可以结合下图来思考:
因为优先级队列除了Insert,其它的都相对比较简单,在这里其它的就不多解释,对于Insert有详细的注解
/**
* 自定义优先级队列
* @author Administrator
*
*/
public class PriorityQ {
private int maxSize;
private long[] QueueArray;
private int nItems;
public PriorityQ(int maxSize) {
this.maxSize = maxSize;
QueueArray = new long[maxSize];
nItems = 0;
}
public void insert(int temp) {
if(!isFull()) {
int j;
//如果nItems里面是空的话,那么就将temp直接赋值给QueueArray[nItems],并将nItems自增
if(nItems==0) {
QueueArray[nItems++] = temp;
}else{
//从第二个开始,跟数组中已有的元素比较,若是比temp小的数,就将这个数往后移,
//这种操作一直持续到找到比temp大的元素,即break,如果没有比temp大的就将其放在第一个位置即QueueArray[0]
for(j=nItems-1;j>=0;j--) {
if(temp>QueueArray[j]) {
QueueArray[j+1] = QueueArray[j];
}else {
break;
}
}
QueueArray[j+1] = temp;
//nItems自增
nItems++;
}
}else {
//若优先级队列是满的则抛出异常
try {
throw new Exception("The Queue is full!");
} catch (Exception e) {
e.printStackTrace();
}
}
}
public String remove() {
if(!isEmpty()) {
return ("Remove successful! The number is:"+QueueArray[--nItems]);
}else {
return ("Sorry!The queue is Empty!");
}
}
public String peekMin() {
if(!isEmpty()) {
return ("Peekmin successful! The Minnumber is:"+QueueArray[nItems-1]);
}else {
return ("Sorry!The queue is Empty!");
}
}
public boolean isEmpty() {
return (nItems==0);
}
public boolean isFull() {
return (nItems==maxSize-1);
}
public int size() {
return nItems;
}
}
/**
* 测试优先级队列
* @author Administrator
*
*/
public class TestPriorityQ {
public static void main(String[] args) {
PriorityQ q = new PriorityQ(10);
System.out.println(q.isEmpty());
q.insert(10);
q.insert(50);
q.insert(30);
q.insert(40);
q.insert(60);
q.insert(80);
q.insert(100);
q.insert(120);
q.insert(110);
System.out.println(q.isFull());
System.out.println(q.peekMin());
System.out.println(q.remove());
System.out.println(q.remove());
System.out.println(q.remove());
System.out.println(q.peekMin());
}
}
结果显示:
true
true
Peekmin successful! The Minnumber is:10
Remove successful! The number is:10
Remove successful! The number is:30
Remove successful! The number is:40
Peekmin successful! The Minnumber is:50
优先级队列的插入操作需要为O(N)的时间,而删除操作只要O(1),我们后面会用堆来改进插入操作的时间。
上一篇: IT巨头样本 微软云落地中国轨迹
下一篇: 集群存储再成热点