优先级队列是不同于先进先出队列的另一种队列。每次去队列的是具有最高优先权的元素。
import java.util.Comparator;
public class PriorityQ<T>
{
private final int SIZE = 20;
private T[] queArray;
private int size;
private final Comparator<? super T> comparator;
public PriorityQ(Comparator<? super T> comparator)
{
queArray = (T[])new Object[SIZE];
this.comparator=comparator;
size = 0;
}
//添加一项,优先级最高的放在数组尾部(队列头部)
public void add(T item)
{
if(isFull()) doubleArray();
int j;
for(j=0; j<size; j++) //找到插入的位置
if( comparator.compare(item,queArray[j])>=0)
break;
for(int k=size-1; k>=j; k--) //移动
queArray[k+1] = queArray[k];
queArray[j] = item;
size++;
}
public void offer(T item){
add(item);
}
//在队列头删除优先级最高的元素并返回
public T poll()
{ return queArray[--size]; }
//从此队列中移除指定元素的单个实例
public boolean remove(T t) {
int i= find(t);
if(i==-1) return false;
removeN(i);
return true;
}
//在优先队列中删除索引为n的项
public void removeN(int n)
{
for(int j=n; j<size-1; j++) // move items down
queArray[j] = queArray[j+1];
size--;
}
//获取但不移除此队列的头
public T peek()
{ return queArray[size-1]; }
public int size()
{ return size; }
public boolean isEmpty()
{ return (size==0); }
public void clear(){
size=0;
}
public T peekN(int n)
{ return queArray[n]; }
public int find(T t)
{
for(int j=0; j<size; j++)
if(comparator.compare(queArray[j],t)==0)
return j;
return -1;
}
private boolean isFull(){
return size==queArray.length;
}
private void doubleArray(){
T [] oldQueue = queArray;
int oldSize = queArray.length;
queArray =(T[])new Object[2*oldSize];
for(int index = 0;index<oldSize;index++){
queArray[index] = oldQueue[index];
}
}
public void display(){
if(size==0) {System.out.println("没有了");return;}
for(int i=0;i<size;i++)
System.out.print(queArray[i]+",");
System.out.println();
}
public static void main(String args[]){
PriorityQ Q=new PriorityQ(new Comparator(){
public int compare(Object o1,Object o2) {
Integer I1=(Integer)o1;
Integer I2=(Integer)o2;
return I1.compareTo(I2);
}
});
for(int i=110;i>0;i--)
Q.offer(new Integer(java.util.concurrent.ThreadLocalRandom.current().nextInt(40)));
Q.display();
System.out.println("===============================");
for(int i=10;i>0;i--)
Q.poll();
Q.display();
System.out.println("===============================");
Q.remove(35);
Q.display();
}
}
下载源码:
分享到:
相关推荐
主要介绍了Java数组模拟优先级队列数据结构的实例,优先级队列中的元素会被设置优先权,本文的例子借助了Java中的TreeSet和TreeMap,需要的朋友可以参考下
具有调整大小数组的优先队列的基本实现
这通常通过遍历数组或使用优先队列来实现。 更新邻居节点的距离: 对于选中的节点,遍历其所有邻居节点。如果通过当前节点到达邻居节点的距离比已知的更短,则更新距离数组中的值。 标记选中的节点为已访问: 将选中...
优先队列 双向链表 二分搜索树 基于二分搜索树的集合 基于链表的集合 基于链表的映射 基于二分搜索树的映射 线段树 字典树 并查集(基于数组索引) 并查集(基于树) 并查集(使用节点size优化) 并查集(使用rank...
Java51.4.1 使用Object表示泛型1.4.2 基本类型的包装1.4.3 使用接口类型表示泛型1.4.4 数组类型的兼容性1.5 利用Java5泛性实现泛型特性成分1.5.1 简单的泛型类和接口1.5.2 自动装箱/拆箱1.5.3 带有限制的通配符...
采用java实现,实现了常用的数据结构,包括顺序表、链表、队列、栈(数组实现和链表实现)、二叉树(二叉排序树)、图(深度优先、广度优先)
Java51.4.1 使用Object表示泛型1.4.2 基本类型的包装1.4.3 使用接口类型表示泛型1.4.4 数组类型的兼容性1.5 利用Java5泛性实现泛型特性成分1.5.1 简单的泛型类和接口1.5.2 自动装箱/拆箱1.5.3 带有限制的通配符...
算法的关键是使用队列来进行遍历。我们从指定的起始顶点开始,并将其入队,并将其标记为已访问。然后,进入循环,直到队列为空。在循环中,我们首先从队列中取出当前顶点,并输出。然后,我们遍历当前顶点的所有邻居...
java5 1.4.1 使用object表示泛型 1.4.2 基本类型的包装 1.4.3 使用接口类型表示泛型 1.4.4 数组类型的兼容性 1.5 利用java5泛性实现泛型特性成分 1.5.1 简单的泛型类和接口 1.5.2 自动装箱/拆箱....
java5 1.4.1 使用object表示泛型 1.4.2 基本类型的包装 1.4.3 使用接口类型表示泛型 1.4.4 数组类型的兼容性 1.5 利用java5泛性实现泛型特性成分 1.5.1 简单的泛型类和接口 1.5.2 自动装箱/拆箱....
Java51.4.1 使用Object表示泛型1.4.2 基本类型的包装1.4.3 使用接口类型表示泛型1.4.4 数组类型的兼容性1.5 利用Java5泛性实现泛型特性成分1.5.1 简单的泛型类和接口1.5.2 自动装箱/拆箱1.5.3 带有限制的通配符...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
小结 练习 参考文献 第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题 6.4.2...
SP 散列堆(优先堆) 二叉堆二项式堆D堆斐波那契堆索引堆左派堆对堆队列基于数组的队列基于链表的队列阻塞队列循环队列具有最大值的队列具有最小值的队列使用两个堆栈实现的队列队列排序一个阵列中的三个队列堆基于...
9.1 单端优先队列和双端优先队列 9.2 左倾树 9.3 二项式堆 9.4 Fibonacci堆 9.5 配偶堆 9.6 对称最小-最大堆 9.7 区间堆 9.8 参考文献和选读材料 第10章 高效二叉查找树 10.1 最优二叉查找树 10.2 AVL树 ...
leetcode二维数组搜索力码 力扣解决方案。 在大多数情况下,始终尝试优化...或者,如果需要某种排序,则使用优先队列(堆)。 关于圆形数组,可能的解决方案是: -- 将数组与其副本连接以获得双倍长度的新数组。 但需
第十五章队列与优先队列 第十六章二叉树 第十七章二叉树的应用 第十八章二叉搜索树 第十九章集与映射 第二十章有序集与映射的实现 第二十一章实现映射的散列法 第二十二章堆 第二十三章位数与文件压缩 第二十四章图...
游戏的任务是使用键盘上的方向健操纵老鼠在规定的时间内走到粮仓处。 基本要求: ⑴老鼠形象可以辨认,可用键盘操纵老鼠上下左右移动; ⑵迷宫的墙足够结实,老鼠不能穿墙而过; ⑶正确检测结果,若老鼠在规定...