Interview(6)Priority Queue

Interview(6)Priority Queue

Priority Queue
Key and Value => Entry

public interface Entry{
    public Object getKey();       //get the key values
    public Object setKey(Object k);
    public object getValue();
    public Object setValue((Object v);
}

public class EntryDefault implements Entry {
    protected Object key;
    protected Object value;

    public EntryDefault(Object k, Object v){
        key = k; value = v;
    }

    public Object getKey() { return key; }
    public Object setKey(Object k) {
        Object oldK = key;
        key = k;
        return oldK;
    }

    public Object getValue() { return value; }
    public Object setValue(Object v) {
        Object oldV = value; value= v; return oldV;
    }
}

Comparator Interface and Implementation

public interface Comparator {
    public int compare(Object a, Object b);
}

compare method will return positive, 0 or negative.

Priority Queue Interface
public interface PriorityQueue {
    public int getSize();
    public boolean isEmpty();
    public Entry getMin() throws ExceptionPriorityQueueEmpty;
    public Entry insert(Object key, Object obj) throw ExceptionKeyInvalid;
    public Entry delMin() throws ExceptionPriorityQueueEmpty;
}

Implementation on top Un Sorted List
public class PriorityQueueUnsortedList implements PriorityQueue {
    private List list;
    private Comparator comparator;

    public PriorityQueuUnsortedList(){
        this(new ComparatorDefault(), null);
    }

    public PriorityQueueUnsortedList(Comparator comparor){ this(c, null); }
    public PriorityQueueUnsortedList(Sequeue s){ this(new ComparatorDefault(), s); }
    public PriorityQueueUnsortedList(Comparator comparator, Sequence sequence){
        list = new ListDLNode();
        comparator = comparator;
        if(null != sequence){
            while(!s.isEmpty()){
                Entry e = (Entry)s.removeFirst();
                insert(e.getKey, e.getValue());
            }
        }
    }

    public int getSize() { return list.getSize();}
    public boolean isEmpty(){ return list.isEmpty(); }
    public Entry getMin() throws ExceptionPriorityQueueEmpty {
        if(list.isEmtpy()){
            throw new ExceptionPriorityQueueEmpty(“Error, queue is empty”);
        }
        Position minPos = list.first();
        Position curPos = list.getNext(minPos);
        while(null != curPos){
            if(0 < comparator.compare(minPos.getElem(), curPos.getElem())){
                minPos = curPos; //find the min one
            }
        }
        return (Entry) minPos.getElem();
    }

    public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid {
        Entry entry = new EntryDefault(key, obj);
        list.insertLast(entry); //put the element at the tail
        return (entry);
    }

    public Entry delMin() throws ExceptionPriorityQueueEmpty {
        if(list.isEmepty()){
            throw new ExceptionPriorityQueueEmpty(“Error”);
        }
        Position minPos = list.first();
        Iterator it = list.pistions();
        while(it.hasNext()){
            Position curPos = (Position) (it.getNext());
            if(  < comprator.compare(
                (Entry)(minPos.getElement()).getKey(),
                (Entry)(curPos.getElement()).getKey()
            )){
                minPos = curPos;
            }
        }
        return (Entry)list.remove(minPos);
    }
}

It is easy to insert, but it is O(n) to getMin() or delMin()

Implementation on top of Sorted List
public class PriorityQueueSortedList implements PriorityQueue {
    private List list;
    private Comparator comparator;

    public PriorityQueueSortedList(){ this(new ComparatorDefault(), null); }
    public PriorityQueueSortedList(Comparator c){ this(c, null); }
    public PriorityQueueSortedList(Sequence s){ this(new ComparatorDefault(), s); }
    public PriorityQueueSortedList(Comparator comparator, Sequence sequence){
        list = new ListDLNode();
        comparator = comparator;
        if( null != s){
            while( !s.isEmpty()) {
                Entry e = (Entry) s. removeFirst();
                insert(e.getKey(), e.getValue());
            }
        }
    }

    public int getSize() { return list.getSize(); }
    public boolean isEmpty() { return list.isEmpty(); }
   
    public Entry getMin() throws ExceptionPriorityQueueEmpty {
        if(list.isEmpty()){
            throw new ExceptionPriorityQueueEmpty(“Error");
        }
        return (Entry) list.last();
    }

    public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid {
        Entry entry = new EntryDefault(key, obj);
        if(list.isEmpty() || (0 > comparator.compare((Entry) (list.first().getElem())).getKey(), entry.getKey()) ){
            list.insertFirst(entry);  //list is empty or current is largest
        }else{
            Position curPos = list.last();
            while( 0 > comparator.compare((Entry) (curPos.getElem())).getKey(), entry.getKey()){
                curPos = list.getPrev(curPos); //move to previous items, find the one bigger than current
            }
            list.insertAfter(curPos, entry);
        }
        return (entry);
    }
   
    public Entry delMin() throws ExceptionPriorityQueueEmpty {
        if(list.isEmpty()){
            throw new ExceptionPriorityQueueEmpty(“Error");
        }
        return (Entry) list.remove(list.last());
    }
}

Heap
Heap Structure - Page 173
Binary Tree - Heap - Big Top - Small Top

public class PriorityQueueHeap implements PriorityQueue {
    private CompleteBinTree h;
    private Comparator comp;

    public PriorityQueueHeap(){  this(new ComparatorDefault(), null); }
    public PriorityQueueHeap(Comparator c){ this(c, null); }
    public PriorityQueueHeap(Sequence s){ this(new ComparatorDefault(), s); }
    public PriorityQueueHeap(Comparator c, Sequence s){
        comp = c;
        h = new CompleteBinTree_Vector(s);
        if( !h.isEmpty()){
            for(int i = h.getSize()/2-1; i>=0; i—){
                precolateDown(h.posOfNode(i));
            }
        }
    }

    public int getSize() { return h.getSize(); }
    public boolean isEmpty() { return h.isEmpty(); }
    public Entry getMin() throws ExceptionPriorityQueueEmpty {
        if(isEmpty()) { throw new ExceptionPriorityQueueEmpty(“Error"); }
        return (Entry) h.getRoot().getElem();
    }

    public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid {
        checkKey(key);
        Entry entry = new EntryDefault(key, obj);
        percolateUp(h.addlast(entry);
        return entry;
    }

    public Entry delMin() throws ExceptionPriorityQueueEmpty {
        if(isEmpty()) { throw new ExceptionPriorityQueueEmpty(“Error”); }
        Entry min = (Entry) h.getRoot().getElem();
        if ( 1 == getSize()) {
            //if it is last item
            h.delLast();
        }else{
            h.getRoot().setElem((ComleBinaryTreeNodeRank)h.delLast().getElme()); //find the last one and place in root
            percolateDown(h.getRoot());
        }
        return min;
    }

    protected void checkKey(Object key) throws ExceptionKeyInvalid {
        try {
            comp.compare(key, key);
        }catch(Exception e){ throw new ExceptionKeyInvalid(); }
    }

    protected Object key(BinTreePosition v){ return ((Entry) (v.getElem())).getKey(); }
    protected void swapParentChild(BinTreePosition u, BinTreePosition v){
        Object temp = u.getElem();
        u.setElem(v.getElem);
        v.setElem(temp);
    }

    protected void percolateUp(BinTreePosition v){
        BinTreePosition root = h.getRoot(); //find the root node
        while( v != h.getRoot()){
            BinTreePosition p = v.getParent(); //get the parent node for current node
            if( 0 >= comp.compare(key(p), key(v))) { break; }
            swapParentChild(p, v); //swap parent and child to move the current node
            v = p;
        }
    }

    protected void precolateDown(BinTreePosition v){
        while (v.hasLChild()){
            BinTreePosition smallerChild = v.getLChild(); //left child is smaller
            if( v.hasRChild() && 0 < comp.compare(key(v.getLChild()), key(v.getRChild()){
                smallerChild = v.getRChild();  //compare right child
            }
            if( 0 <= comp.compare(key(smallerChild), key(v) ){ break; }
            swapParentChild(v, smallerChild);
            v = smallerChild;
        }
    }
}



References: