0001 /* 0002 * 基于优先队列的排序器 0003 */ 0004 0005 package dsa; 0006 0007 public class Sorter_PQueue implements Sorter { 0008 private Comparator C; 0009 0010 public Sorter_PQueue() 0011 { this(new ComparatorDefault()); } 0012 0013 public Sorter_PQueue(Comparator comp) 0014 { C = comp; } 0015 0016 public void sort(Sequence S) { 0017 Sequence T = new Sequence_DLNode();//为批处理建立优先队列而准备的序列 0018 while (!S.isEmpty()) {//构建序列T 0019 Object e = S.removeFirst();//逐一取出S中各元素 0020 T.insertLast(new EntryDefault(e, e));//用节点元素本身作为关键码 0021 } 0022 // PQueue pq = new PQueue_UnsortedList(C, T); 0023 // PQueue pq = new PQueue_SortedList(C, T); 0024 PQueue pq = new PQueue_Heap(C, T); 0025 while(!pq.isEmpty()) {//从优先队列中不断地 0026 S.insertLast(pq.delMin().getValue());//取出最小元素,插至序列末尾 0027 System.out.println("\t:\t" + S.last().getElem()); 0028 } 0029 } 0030 }