homedukeAlgorithmen & Datenstrukturen mit Java: Beispielklasse für Vorrang-Warteschlangen Prof. Dr. Uwe Schmidt FH Wedel

Beispielklasse für Vorrang-Warteschlangen

weiter

weiter

Priority Queue
eine sehr schmale Schnittstelle
weiter
   1package ds.interfaces;
   2
   3/** Simple interface for maps
   4 */
   5
   6import java.util.Iterator;
   7
   8import ds.util.Invariant;
   9import ds.util.Function2;
  10
  11import ds.util.P;  // example class for priorities
  12import ds.util.V;  // example class for values
  13import ds.util.PV// priority-value pair
  14
  15public
  16    interface PriorityQueue
  17    extends Iterable<PV>,
  18            Invariant {
  19
  20    boolean       isEmpty();
  21    int           size();
  22    PV            findMin();
  23    PriorityQueue insert(P pV v);
  24    PriorityQueue removeMin();
  25    PriorityQueue copy();
  26
  27    // inherited
  28
  29    // public Iterator<PV> iterator();
  30    // public inv();
  31}
weiter
Implementierung
als binäre Halde in der Variante als schiefe Halde (skew heap)
ohne Generics
persistente Implementierung
destruktive Implementierung in Kommentar
weiter
   1package ds.persistent.queue;
   2
   3/** Persistent implementation of binary heap tree.
   4    Operations manipulating trees always create copies
   5    of the objects to be manipulated. This assures, that
   6    old trees remains unchanged.
   7
   8    Binary heap trees require a total ordering
   9    on the priority value.
  10*/
  11
  12import ds.interfaces.PriorityQueue;
  13
  14import ds.util.P;         // example class for prios
  15import ds.util.V;         // example class for values
  16import ds.util.PV;        // prio value pair
  17
  18import static ds.util.PV.mkPair;
  19import static ds.util.Integer.max;
  20import static ds.util.Integer.min;
  21import static ds.util.Undef.undefined;
  22
  23import java.util.Iterator;
  24
  25import static java.lang.Integer.signum;
  26
  27//----------------------------------------
  28
  29public abstract
  30    class BinaryHeap
  31    implements PriorityQueue {
  32
  33    //----------------------------------------
  34    // the smart constructors
  35
  36    // empty list
  37    public static
  38        BinaryHeap empty() {
  39        return
  40            EMPTY;
  41    }
  42
  43    // singleton list
  44    public static
  45        BinaryHeap singleton(P pV v) {
  46        return
  47            new Node(pvEMPTYEMPTY);
  48    }
  49
  50    // build search tree from arbitrary sequence (iterator)
  51    public static
  52        BinaryHeap fromIterator(Iterator<PV> elems) {
  53
  54        BinaryHeap res = empty();
  55        while ( elems.hasNext() ) {
  56            PV p = elems.next();
  57            res = res.insert(p.fstp.snd);
  58        }
  59        return
  60            res;
  61    }
  62
  63    //----------------------------------------
  64    // public methods
  65
  66    public abstract BinaryHeap insert(P pV v);
  67    public abstract BinaryHeap removeMin();
  68
  69    public String toString() {
  70        return 
  71            iterator().toString();
  72    }
  73
  74    public Iterator<PV> iterator() {
  75        return
  76            new HeapIterator(this);
  77    }
  78
  79    public BinaryHeap copy() {
  80        return
  81            this;
  82    }
  83
  84    //----------------------------------------
  85    // special binary tree methods
  86
  87    abstract public int depth();
  88    abstract public int minDepth();
  89
  90    //----------------------------------------
  91    // internal methods
  92
  93    // helper
  94    abstract boolean childGE(P p);
  95
  96    abstract BinaryHeap merge(BinaryHeap h2);
  97    abstract BinaryHeap merge2(Node n1);
  98
  99    private static <A> A nodeExpected() {
 100        return
 101            undefined("Node expected");
 102    }  
 103
 104    //----------------------------------------
 105    // the empty tree implemented by applying
 106    // the singleton design pattern
 107
 108    // the "generic" empty tree object
 109
 110    private static final BinaryHeap EMPTY
 111        = new Empty();
 112
 113    // the singleton class for the empty tree object
 114
 115    private static final
 116        class Empty
 117        extends BinaryHeap {
 118
 119        // predicates and attributes
 120        public boolean isEmpty() {
 121            return true;
 122        }
 123
 124        public int size() {
 125            return 0;
 126        }
 127
 128        public int depth() {
 129            return 0;
 130        }
 131
 132        public int minDepth() {
 133            return 0;
 134        }
 135
 136        public PV findMin() {
 137            return nodeExpected();
 138        }
 139  
 140        public BinaryHeap insert(P pV v) {
 141            return
 142                singleton(pv);
 143        }
 144
 145        public BinaryHeap removeMin() {
 146            return nodeExpected();
 147        }
 148
 149        public boolean inv() {
 150            return true;
 151        }
 152
 153        //----------------------------------------
 154        // not public stuff
 155
 156        Empty() { }
 157
 158        boolean childGE(P p) {
 159            return true;
 160        }
 161
 162        BinaryHeap merge(BinaryHeap h2) {
 163            return h2;
 164        }
 165        BinaryHeap merge2(Node n1) {
 166            return n1;
 167        }
 168
 169    }
 170    
 171    //----------------------------------------
 172    // the node class for none empty trees
 173
 174    private static final
 175        class Node
 176        extends BinaryHeap {
 177
 178        /* persistent */
 179        final P          p;
 180        final V          v;
 181        final BinaryHeap l;
 182        final BinaryHeap r;
 183
 184        /* destructive *
 185        P          p;
 186        V          v;
 187        BinaryHeap l;
 188        BinaryHeap r;
 189        /**/
 190
 191        Node(P pV vBinaryHeap lBinaryHeap r) {
 192            assert p != null;
 193
 194            this.p = p;
 195            this.v = v;
 196            this.l = l;
 197            this.r = r;
 198            ++cntNode;
 199        }
 200
 201        //----------------------------------------
 202        // predicates and attributes
 203
 204        public boolean isEmpty() {
 205            return false;
 206        }
 207
 208        public int size() {
 209            return
 210                1 + l.size() + r.size();
 211        }
 212
 213        public int depth() {
 214            return
 215                1 + max(l.depth()r.depth());
 216        }
 217
 218        public int minDepth() {
 219            return
 220                1 + min(l.minDepth()r.minDepth());
 221        }
 222
 223        public PV findMin() {
 224            return
 225                mkPair(pv);
 226        }  
 227
 228        public BinaryHeap insert(P pV v) {
 229            return
 230                this.merge(singleton(pv));
 231        }
 232    
 233        public BinaryHeap removeMin() {
 234            // forget the root
 235            return
 236                l.merge(r);
 237        }
 238
 239        /* destructive *
 240        public BinaryHeap copy() {
 241            return
 242                new Node(p, v,
 243                         l.copy(),
 244                         r.copy());
 245        }
 246        /**/
 247
 248        public boolean inv() {
 249            return
 250                l.childGE(p)
 251                &&
 252                r.childGE(p)
 253                &&
 254                l.inv()
 255                &&
 256                r.inv();
 257        }
 258
 259        //----------------------------------------
 260        // internal methods
 261
 262        // helper for inv
 263        boolean childGE(P p) {
 264            return
 265                this.p.compareTo(p) >= 0;
 266        }
 267
 268        // the workers: merge and join
 269        // merge and merge2 simulate double dispatch
 270        // over both heaps
 271
 272        BinaryHeap merge(BinaryHeap h2) {
 273            return
 274                h2.merge2(this);
 275        }
 276
 277        BinaryHeap merge2(Node n1) {
 278            if ( this.p.compareTo(n1.p) <= 0)
 279                return
 280                    this.join(n1);
 281            return
 282                n1.join(this);
 283        }
 284
 285        BinaryHeap join(Node n2) {
 286            return
 287                setLR(this.rthis.l.merge(n2));
 288        }
 289
 290        // setter
 291
 292        private Node setLR(BinaryHeap lBinaryHeap r) {
 293            /* persistent */
 294            if ( l == this.l && r == this.r )
 295                return
 296                    this;
 297            return
 298                new Node(this.pthis.vlr);
 299
 300            /* destructive *
 301            this.l = l;
 302            this.r = r;
 303            return
 304                this;
 305            /**/
 306        }
 307
 308    } // end Node
 309
 310    //----------------------------------------
 311    // iterator
 312    // ascending enumeration
 313
 314    private static
 315        class HeapIterator
 316        extends ds.util.Iterator<PV> {
 317        
 318        BinaryHeap queue;
 319
 320        HeapIterator(BinaryHeap n) {
 321            /* persistent */
 322            queue = n;
 323
 324            /* destructive *
 325            // we need a copy of the heap,
 326            // else the queue is destroied by the iterator
 327            queue = n.copy();
 328
 329            /**/
 330            ++cntIter;
 331        }
 332
 333        public boolean hasNext() {
 334            return
 335                ! queue.isEmpty();
 336        }
 337
 338        public PV next() {
 339            if ( queue.isEmpty() )
 340                return
 341                    undefined("empty heap");
 342
 343            PV res = queue.findMin();
 344            queue  = queue.removeMin();
 345            return
 346                res;
 347        }
 348    }   // end HeapIterator
 349
 350    //----------------------------------------
 351    // profiling
 352
 353    private static int cntNode = 0;
 354    private static int cntIter = 0;
 355
 356    public static String stats() {
 357        return
 358            "stats for ds.persistent.queue.BinaryHeap:\n" +
 359            "# new Node()               : " + cntNode + "\n" +
 360            "# new Iterator()           : " + cntIter + "\n";
 361    }
 362
 363    public String objStats() {
 364        int s = size();
 365        int o = s;
 366        int f = 4 * s;
 367        int m = o + f;
 368
 369        return
 370            "mem stats for ds.persistent.queue.BinaryHeap object:\n" +
 371            "# elements (size)      : " + s + "\n" +
 372            "# objects              : " + o + "\n" +
 373            "# fields               : " + f + "\n" +
 374            "# mem words            : " + m + "\n";
 375    }
 376}
weiter
Quellen
weiter

Letzte Änderung: 10.12.2015
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel