学着书上的写了一个优先队列，用堆实现。笔记一下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | package com.zerob13.PriorityQueue; /** * * @author yanglingfeng */ public class PriorityQueue { private static final int def_size=10; private Comparable[] array; private int count; /** * 初始化函数 */ public PriorityQueue(){ array=new Comparable[def_size]; count=0; } /** * 清理函数 */ public void clear(){ for(int i=0;i<count;i++) array[i]=null; count=0; } /** * 添加一个元素 * @param val */ public void add(Comparable val){ if(count==array.length)expand(); int curr=count++; while(curr>0){ int parent=(curr-1)/2; if(val.compareTo(array[parent])>0) break; array[curr]=array[parent]; curr=parent; } array[curr]=val; } /** * 移除顶端元素 * @return 最小元素 */ public Comparable remove(){ if(count==0) return null; Comparable min=array[0]; Comparable last=array[--count]; array[count]=null; int child,curr=0; while((child=2*curr+1)<count){ if(child+1<count&&array[child+1].compareTo(array[child])<0) child++; if(last.compareTo(array[child])<=0) break; array[curr]=array[child]; curr=child; } array[curr]=last; return min; } /** * 判断是否为空队列 * @return boolean */ public boolean isEmpty(){ return count==0; } /** * 返回大小 * @return int */ public int size(){ return count; } /** * 返回最小值 * @return minval */ public Comparable getMin(){ if(count==0) return null; return array[0]; } private void expand(){ Comparable[] newArray=new Comparable[2*array.length]; for(int i=0;i<array.length;i++) newArray[i]=array[i]; array=newArray; } @Override public String toString(){ String buf=""; int i=0; int j=1; int k=0; while(i<count){ if(k<j){ buf+=array[i++]+" "; k++; }else{ buf+=array[i++]+" "; k=0; j*=2; } } return buf; } } |
