Algorithmen & Datenstrukturen mit Java: Beispielklasse für Vorrang-Warteschlangen

Priority Queue	eine sehr schmale Schnittstelle

package ds.interfaces;
/** Simple interface for maps
 */
import java.util.Iterator;
import ds.util.Invariant;
import ds.util.Function2;
import ds.util.P;  // example class for priorities
import ds.util.V;  // example class for values
import ds.util.PV; // priority-value pair
public
    interface PriorityQueue
    extends Iterable<PV>,
            Invariant {
    boolean       isEmpty();
    int           size();
    PV            findMin();
    PriorityQueue insert(P p, V v);
    PriorityQueue removeMin();
    PriorityQueue copy();
    // inherited
    // public Iterator<PV> iterator();
    // public inv();
}

Implementierung	als binäre Halde in der Variante als schiefe Halde (skew heap)
	ohne Generics
	persistente Implementierung
	destruktive Implementierung in Kommentar

package ds.persistent.queue;
/** Persistent implementation of binary heap tree.
    Operations manipulating trees always create copies
    of the objects to be manipulated. This assures, that
    old trees remains unchanged.
    Binary heap trees require a total ordering
    on the priority value.
*/
import ds.interfaces.PriorityQueue;
import ds.util.P;         // example class for prios
import ds.util.V;         // example class for values
import ds.util.PV;        // prio value pair
import static ds.util.PV.mkPair;
import static ds.util.Integer.max;
import static ds.util.Integer.min;
import static ds.util.Undef.undefined;
import java.util.Iterator;
import static java.lang.Integer.signum;
//----------------------------------------
public abstract
    class BinaryHeap
    implements PriorityQueue {
    //----------------------------------------
    // the smart constructors
    // empty list
    public static
        BinaryHeap empty() {
        return
            EMPTY;
    }
    // singleton list
    public static
        BinaryHeap singleton(P p, V v) {
        return
            new Node(p, v, EMPTY, EMPTY);
    }
    // build search tree from arbitrary sequence (iterator)
    public static
        BinaryHeap fromIterator(Iterator<PV> elems) {
        BinaryHeap res = empty();
        while ( elems.hasNext() ) {
            PV p = elems.next();
            res = res.insert(p.fst, p.snd);
        }
        return
            res;
    }
    //----------------------------------------
    // public methods
    public abstract BinaryHeap insert(P p, V v);
    public abstract BinaryHeap removeMin();
    public String toString() {
        return 
            iterator().toString();
    }
    public Iterator<PV> iterator() {
        return
            new HeapIterator(this);
    }
    public BinaryHeap copy() {
        return
            this;
    }
    //----------------------------------------
    // special binary tree methods
    abstract public int depth();
    abstract public int minDepth();
    //----------------------------------------
    // internal methods
    // helper
    abstract boolean childGE(P p);
    abstract BinaryHeap merge(BinaryHeap h2);
    abstract BinaryHeap merge2(Node n1);
    private static <A> A nodeExpected() {
        return
            undefined("Node expected");
    }  
    //----------------------------------------
    // the empty tree implemented by applying
    // the singleton design pattern
    // the "generic" empty tree object
    private static final BinaryHeap EMPTY
        = new Empty();
    // the singleton class for the empty tree object
    private static final
        class Empty
        extends BinaryHeap {
        // predicates and attributes
        public boolean isEmpty() {
            return true;
        }
        public int size() {
            return 0;
        }
        public int depth() {
            return 0;
        }
        public int minDepth() {
            return 0;
        }
        public PV findMin() {
            return nodeExpected();
        }
  
        public BinaryHeap insert(P p, V v) {
            return
                singleton(p, v);
        }
        public BinaryHeap removeMin() {
            return nodeExpected();
        }
        public boolean inv() {
            return true;
        }
        //----------------------------------------
        // not public stuff
        Empty() { }
        boolean childGE(P p) {
            return true;
        }
        BinaryHeap merge(BinaryHeap h2) {
            return h2;
        }
        BinaryHeap merge2(Node n1) {
            return n1;
        }
    }
    
    //----------------------------------------
    // the node class for none empty trees
    private static final
        class Node
        extends BinaryHeap {
        /* persistent */
        final P          p;
        final V          v;
        final BinaryHeap l;
        final BinaryHeap r;
        /* destructive *
        P          p;
        V          v;
        BinaryHeap l;
        BinaryHeap r;
        /**/
        Node(P p, V v, BinaryHeap l, BinaryHeap r) {
            assert p != null;
            this.p = p;
            this.v = v;
            this.l = l;
            this.r = r;
            ++cntNode;
        }
        //----------------------------------------
        // predicates and attributes
        public boolean isEmpty() {
            return false;
        }
        public int size() {
            return
                1 + l.size() + r.size();
        }
        public int depth() {
            return
                1 + max(l.depth(), r.depth());
        }
        public int minDepth() {
            return
                1 + min(l.minDepth(), r.minDepth());
        }
        public PV findMin() {
            return
                mkPair(p, v);
        }  
        public BinaryHeap insert(P p, V v) {
            return
                this.merge(singleton(p, v));
        }
    
        public BinaryHeap removeMin() {
            // forget the root
            return
                l.merge(r);
        }
        /* destructive *
        public BinaryHeap copy() {
            return
                new Node(p, v,
                         l.copy(),
                         r.copy());
        }
        /**/
        public boolean inv() {
            return
                l.childGE(p)
                &&
                r.childGE(p)
                &&
                l.inv()
                &&
                r.inv();
        }
        //----------------------------------------
        // internal methods
        // helper for inv
        boolean childGE(P p) {
            return
                this.p.compareTo(p) >= 0;
        }
        // the workers: merge and join
        // merge and merge2 simulate double dispatch
        // over both heaps
        BinaryHeap merge(BinaryHeap h2) {
            return
                h2.merge2(this);
        }
        BinaryHeap merge2(Node n1) {
            if ( this.p.compareTo(n1.p) <= 0)
                return
                    this.join(n1);
            return
                n1.join(this);
        }
        BinaryHeap join(Node n2) {
            return
                setLR(this.r, this.l.merge(n2));
        }
        // setter
        private Node setLR(BinaryHeap l, BinaryHeap r) {
            /* persistent */
            if ( l == this.l && r == this.r )
                return
                    this;
            return
                new Node(this.p, this.v, l, r);
            /* destructive *
            this.l = l;
            this.r = r;
            return
                this;
            /**/
        }
    } // end Node
    //----------------------------------------
    // iterator
    // ascending enumeration
    private static
        class HeapIterator
        extends ds.util.Iterator<PV> {
        
        BinaryHeap queue;
        HeapIterator(BinaryHeap n) {
            /* persistent */
            queue = n;
            /* destructive *
            // we need a copy of the heap,
            // else the queue is destroied by the iterator
            queue = n.copy();
            /**/
            ++cntIter;
        }
        public boolean hasNext() {
            return
                ! queue.isEmpty();
        }
        public PV next() {
            if ( queue.isEmpty() )
                return
                    undefined("empty heap");
            PV res = queue.findMin();
            queue  = queue.removeMin();
            return
                res;
        }
    }   // end HeapIterator
    //----------------------------------------
    // profiling
    private static int cntNode = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.persistent.queue.BinaryHeap:\n" +
            "# new Node()               : " + cntNode + "\n" +
            "# new Iterator()           : " + cntIter + "\n";
    }
    public String objStats() {
        int s = size();
        int o = s;
        int f = 4 * s;
        int m = o + f;
        return
            "mem stats for ds.persistent.queue.BinaryHeap object:\n" +
            "# elements (size)      : " + s + "\n" +
            "# objects              : " + o + "\n" +
            "# fields               : " + f + "\n" +
            "# mem words            : " + m + "\n";
    }
}

Quellen
	interface PriorityQueue
	class BinaryHeap
	class P
	class V
	class PV
	class Iterator
	class Invariant
	class Undef