首页 > itarticle > list

list

admin 11月 14, 2020 0

Priority Queue: A a collection of prioritized elements that allows arbitrary element insertion, and allows the removal of the element that has first priority..
When an element is added to a priority queue, the user designates its priority by providing an associated key. The element with the minimal key will be the next to be removed from the queue

Iterface && Abstract Class & Comparator

public interface PriorityQueue<K, V> {
    int size();
    boolean isEmpty();
    Entry<K, V> insert(K key, V value) throws IllegalArgumentException;
    Entry<K, V> removeMin();
    Entry<K, V> min();
}

public interface Entry<K, V> {
    K getKey();
    V getValue();
}

import java.util.Comparator;

public class DefaultComparator<E> implements Comparator<E> {
    @Override
    public int compare(E o1, E o2) throws ClassCastException {
        return ((Comparable<E>) o1).compareTo(o2);
    }
}

import java.util.Comparator;

public abstract class AbstractPriorityQueue<K, V> implements PriorityQueue<K, V> {
    protected static class PQEntry<K, V> implements Entry<K, V> {
        K key;
        V value;
        public PQEntry(K k, V v) {
            key = k;
            value = v;
        }
        @Override
        public K getKey() { return key; }
        @Override
        public V getValue() { return value; }
        protected void setKey(K k) { key = k; }
        protected void setValue(V v) { value = v; }
    }

    private Comparator<K> comp;

    protected AbstractPriorityQueue(Comparator<K> c) { comp = c; }
    protected  AbstractPriorityQueue() {this(new DefaultComparator<>());}

    protected int compare(Entry<K, V> e1, Entry<K, V> e2) { return comp.compare(e1.getKey(), e2.getKey());}
    protected boolean checkKey(K key) throws IllegalArgumentException {
        try {
            return comp.compare(key, key) == 0;
        } catch (ClassCastException e) {
            throw new IllegalArgumentException("Incompatible Key");
        }
    }
    @Override
    public boolean isEmpty() { return size() == 0; }
}

Implementing a Priority Queue with an Unsorted List

public class UnsortedPriorityQueue<K, V> extends AbstractPriorityQueue<K, V> {
    private PositionalList<Entry<K ,V>> list = new LinkedPositionalList<>();

    public UnsortedPriorityQueue() { super(); }
    public UnsortedPriorityQueue(Comparator<K> c) { super(c); }

    private Position<Entry<K, V>> findMin() {
        Position<Entry<K, V>> min = list.first();
        for (Position<Entry<K, V>> each : list.positions()){
            if (compare(each.getElement(), min.getElement()) < 0) min = each;
        }
        return min;
    }
    @Override
    public int size() { return list.size(); }
    @Override
    public Entry<K, V> insert(K key, V value) throws IllegalArgumentException {
        checkKey(key);
        Entry<K, V> newEntry = new PQEntry<>(key, value);
        list.addLast(newEntry);
        return newEntry;
    }
    @Override
    public Entry<K, V> removeMin() {
        return list.remove(findMin());
    }

    @Override
    public Entry<K, V> min() {
        return findMin().getElement();
    }
}

Implementing a Priority Queue with a Sorted List

public class SortedPriorityQueue<K, V> extends AbstractPriorityQueue<K, V> {
    private PositionalList<Entry<K, V>> list = new LinkedPositionalList<>();

    public SortedPriorityQueue(Comparator<K> c) { super(c); }
    public SortedPriorityQueue() { super(); }

    @Override
    public int size() { return list.size(); }
    @Override
    public Entry<K, V> insert(K key, V value) throws IllegalArgumentException {
        checkKey(key);
        Entry<K, V> newEntry = new PQEntry<>(key, value);
        boolean isAdd = false;
        for (Position<Entry<K, V>> each : list.positions()) {
            if (compare(each.getElement(), newEntry) > 0) {
                list.addBefore(each, newEntry);
                isAdd = true;
                break;
            }
        }
        if (!isAdd) list.addLast(newEntry);
        return newEntry;
    }

    @Override
    public Entry<K, V> removeMin() {
        if (isEmpty()) return null;
        return list.remove(list.first());
    }
    @Override
    public Entry<K, V> min() {
        if (isEmpty()) return null;
        return list.first().getElement();
    }
}