class PriorityQueue{
private Comparable[] array;
private int index;
public PriorityQueue(){
array=new Comparable[16];
index=0;
}
public boolean isEmpty(){
return index==0;
}
public void add(Comparable item){
if(index==array.length){
resize();
}
array[index]=item;
index++;
}
private void resize(){
Comparable[] newArray=new Comparable[array.length*2];
//we assume that the old array if full
for(int i=0;i<array.length;i++){
newArray[i]=array[i];
}
array=newArray;
}
public Comparable remove(){
if(index==0) return null;
int maxIndex=0;
//find the index of the item with the highest priority
for(int i=1;i<index;i++){
if(array[i].compareTo(array[maxIndex])>0){
maxIndex=i;
}
}
Comparable result=array[maxIndex];
//move the last item into the empty slot
index--;
array[maxIndex]=array[index];
return result;
}
//无法掩饰对remove()的喜爱
}
//优先队列的数组实施
//高尔夫球手记分类
public class Golfer implements Comparable
{
String name;
int score;
public Golfer(String name,int score){
this.name=name;
this.score=score;
}
public int compareTo(Object obj){
Golfer that=(Golfer)obj;
int a=this.score;
int b=that.score;
//for golfers,low is good!
if(a<b) return 1;
if(a>b) return -1;
return 0;
}
public static void main(String args[]){
PriorityQueue pq=new PriorityQueue();
Integer item1=new Integer(2);
pq.add(item1);
Integer item2=new Integer(1);
pq.add(item2);
Integer item3=new Integer(3);
pq.add(item3);
while(!pq.isEmpty()){
Integer item=(Integer)pq.remove();
System.out.println(item);
}
Golfer tiger=new Golfer("Tiger Woods",61);
Golfer phil=new Golfer("Phil Mickelson",72);
Golfer hal=new Golfer("Hal Sutton",69);
pq.add(tiger);
pq.add(phil);
pq.add(hal);
while(!pq.isEmpty()){
Golfer golfer=(Golfer)pq.remove();
System.out.println(golfer.name+"\t"+golfer.score);
}
}
}
分享到:
相关推荐
用C语言实现一个优先队列;压缩文件中包括三个文件:1.HeapQueue.h优先队列源代码,2.main.cpp测试主函数;3.HeapQueue.h使用说明
编写优先队列数据(priority_queue)类型,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作...
C语言 堆 优先队列
可嵌入到matlab中的优先队列,包括pq_create,插入,删去,取顶端,
优先队列-java可以选择属性和升序降序
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看
优先队列.rar 优先队列.rar 优先队列.rar 优先队列.rar
数据结构,课程设计优先队列实验报告 用最大堆实现的优先队列
数据结构优先队列,是一个简易版优先队列,输入数据及权值可以对其进行插入,删除等操作。
优先队列的实现,简单实用,实现一个按ttl时间优先的优先队列
利用堆实现的优先队列实质是一棵顺序存储的二叉树!所以具有很好的时间"空间性能!比传统的优先队列具有更广泛的应用前景!可在计算机的各种排队算法中推广应用
讲STL的栈,队列,优先队列,内有代码清单使用方法等等
优先队列课程设计
用头文件封装的优先队列!可以进行插入、查找、删除等操作!
本程序主要由堆来实现优先队列的数据结构,主要有优先队列的删除,插入。算法复杂度为logn
一. 优先队列的定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除。 本程序的实现 二. 实现本优先队列的初始化,查找,插入,删除操作,...
本文提出一种基于K 叉树的优先队列的算法, 通过建立K 叉树堆的数据结构, 从n 个元素中 得到m 个元素的优先队列, 其算法的最坏时间复杂度为O (2m log2n + 2n ). 本算法是基于二叉树堆 的优先队列算法的推广, 并具有较...
构建最大堆,维护最大堆,堆排序,以及对在优先队列中的应用。对最大优先队列执行以下操作:向队列中插入新元素,增加某个元素的值,去掉并返回队列中的最大值并保证最大队的性质
数据结构 基于链表实现的优先队列 Cpp文件