0001 /* 0002 * 利用堆实现优先队列 0003 */ 0004 0005 package dsa; 0006 0007 public class PQueue_Heap implements PQueue { 0008 private ComplBinTree H;//完全二叉树形式的堆 0009 private Comparator comp;//比较器 0010 0011 //构造方法 0012 public PQueue_Heap() 0013 { this(new ComparatorDefault(), null); } 0014 0015 //构造方法:默认的空优先队列 0016 public PQueue_Heap(Comparator c) 0017 { this(c, null); } 0018 0019 //构造方法:根据某一序列直接批量式构造堆算法,S中元素都是形如(key, value)的条目 0020 public PQueue_Heap(Sequence S) 0021 { this(new ComparatorDefault(), S); } 0022 0023 //构造方法:根据某一序列直接批量式构造堆算法,s中元素都是形如(key, value)的条目 0024 public PQueue_Heap(Comparator c, Sequence s) { 0025 comp = c; 0026 H = new ComplBinTree_Vector(s); 0027 if (!H.isEmpty()) { 0028 for (int i = H.getSize() / 2 - 1; i >= 0; i--) //自底而上 0029 percolateDown(H.posOfNode(i));//逐节点进行下滤 0030 } 0031 } 0032 0033 /*-------- PQueue接口中定义的方法 --------*/ 0034 //统计优先队列的规模 0035 public int getSize() 0036 { return H.getSize(); } 0037 0038 //判断优先队列是否为空 0039 public boolean isEmpty() 0040 { return H.isEmpty(); } 0041 0042 //若Q非空,则返回其中的最小条目(并不删除);否则,报错 0043 public Entry getMin() throws ExceptionPQueueEmpty { 0044 if (isEmpty()) throw new ExceptionPQueueEmpty("意外:优先队列为空"); 0045 return (Entry) H.getRoot().getElem(); 0046 } 0047 0048 //将对象obj与关键码k合成一个条目,将其插入Q中,并返回该条目 0049 public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid { 0050 checkKey(key); 0051 Entry entry = new EntryDefault(key, obj); 0052 percolateUp(H.addLast(entry)); 0053 return entry; 0054 } 0055 0056 //若Q非空,则从其中摘除关键码最小的条目,并返回该条目;否则,报错 0057 public Entry delMin() throws ExceptionPQueueEmpty { 0058 if (isEmpty()) throw new ExceptionPQueueEmpty("意外:优先队列为空"); 0059 Entry min = (Entry)H.getRoot().getElem();//保留堆顶 0060 if (1 == getSize())//若只剩下最后一个条目 0061 H.delLast();//直接摘除之 0062 else {//否则 0063 H.getRoot().setElem(((ComplBinTreeNode_Rank)H.delLast()).getElem()); 0064 //取出最后一个条目,植入堆顶 0065 percolateDown(H.getRoot()); 0066 } 0067 return min;//返回原堆顶 0068 } 0069 0070 /*-------- 辅助方法 --------*/ 0071 //检查关键码的可比较性 0072 protected void checkKey(Object key) throws ExceptionKeyInvalid { 0073 try { 0074 comp.compare(key, key); 0075 } catch (Exception e) { 0076 throw new ExceptionKeyInvalid("无法比较关键码"); 0077 } 0078 } 0079 0080 //返回节点v(中所存条目)的关键码 0081 protected Object key(BinTreePosition v) { 0082 return ((Entry)(v.getElem())).getKey(); 0083 } 0084 0085 /*-------- 算法方法 --------*/ 0086 //交换父子节点(中所存放的内容) 0087 protected void swapParentChild(BinTreePosition u, BinTreePosition v) { 0088 Object temp = u.getElem(); 0089 u.setElem(v.getElem()); 0090 v.setElem(temp); 0091 } 0092 0093 //上滤算法 0094 protected void percolateUp(BinTreePosition v) { 0095 BinTreePosition root = H.getRoot();//记录根节点 0096 while (v != H.getRoot()) {//不断地 0097 BinTreePosition p = v.getParent();//取当前节点的父亲 0098 if (0 >= comp.compare(key(p), key(v))) break;//除非父亲比孩子小 0099 swapParentChild(p, v);//否则,交换父子次序 0100 v = p;//继续考察新的父节点(即原先的孩子) 0101 } 0102 } 0103 0104 //下滤算法 0105 protected void percolateDown(BinTreePosition v) { 0106 while (v.hasLChild()) {//直到v成为叶子 0107 BinTreePosition smallerChild = v.getLChild();//首先假设左孩子的(关键码)更小 0108 if (v.hasRChild() && 0 < comp.compare(key(v.getLChild()), key(v.getRChild()))) 0109 smallerChild = v.getRChild();//若右孩子存在且更小,则将右孩子作为进一步比较的对象 0110 if (0 <= comp.compare(key(smallerChild), key(v))) break;//若两个孩子都不比v更小,则下滤完成 0111 swapParentChild(v, smallerChild);//否则,将其与更小的孩子交换 0112 v = smallerChild;//并继续考察这个孩子 0113 } 0114 } 0115 }