如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样,我们就引入了优先级队列 这种数据结构。 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 。对于优先权相同的元素,可按先进先出次序处理或按任意优先权进行。
具体代码实现:
1 package data.struct.algorithm; 2 3 //优先级队列 4 class PriorityQueue{ 5 private int maxSize; 6 private int[] queueArray; 7 private int nItems; 8 public PriorityQueue(int s){ 9 maxSize=s; 10 queueArray=new int[maxSize]; 11 nItems=0; 12 } 13 public void enQueue(int value){ 14 int j; 15 if(this.isFull()){ 16 throw new RuntimeException("优先级队列已满"); 17 } 18 if(nItems==0){ 19 queueArray[nItems++]=value; 20 } 21 else { 22 for(j=nItems-1;j>=0;j--){ 23 if(value>queueArray[j]){ 24 queueArray[j+1]=queueArray[j]; 25 } 26 else { 27 break; 28 } 29 } 30 queueArray[j+1]=value; 31 nItems++; 32 } 33 } 34 public int deQueue(){ 35 return queueArray[--nItems]; 36 } 37 public int peek(){ 38 return queueArray[nItems-1]; 39 } 40 public boolean isEmpty(){ 41 return nItems==0; 42 } 43 public boolean isFull(){ 44 return nItems==maxSize; 45 } 46 } 47 public class PriorityQueueDemo { 48 49 /** 50 * @param args 51 */ 52 public static void main(String[] args) { 53 54 PriorityQueue pQueue=new PriorityQueue(5); 55 pQueue.enQueue(5); 56 pQueue.enQueue(10); 57 pQueue.enQueue(6); 58 pQueue.enQueue(63); 59 pQueue.enQueue(89); 60 System.out.println(pQueue.deQueue()); 61 System.out.println(pQueue.peek()); 62 while(!pQueue.isEmpty()){ 63 System.out.print(pQueue.deQueue()+" "); 64 } 65 System.out.println(); 66 } 67 68 }