Basisklassen

import java.util.ArrayList;

public class PriorityQueue<Type>
{
    private ArrayList<Pair<Double, Type>> a;
    private int updown;  // extract liefert Maximum (+1) oder Minimum (-1)

    public PriorityQueue(int updown_)
    {
        a=new ArrayList<Pair<Double, Type>>();
        updown=updown_;
    }

    public PriorityQueue()
    {
        this(1);
    }
   
    // Objekt x mit Priorität p einfügen
    public void insert(double p, Type x)
    {
        a.add(new Pair<Double, Type>(p, x));    // an ArrayList anhängen
        upheap();
    }

    // Eintrag maximaler Priorität zurückgeben und löschen
    public Pair<Double, Type> extract()
    {
        Pair<Double, Type> z;
        exchange(root(), lastLeaf());
        z=a.remove(lastLeaf());
        downheap();
        return z;
    }

    // Objekt maximaler Priorität zurückgeben und löschen
    public Type extractObj()
    {
        return extract().get1();
    }

    private void upheap()
    {
        int u, v=lastLeaf();
        while (!isRoot(v))      // v ist nicht die Wurzel
        {   
            u=pred(v);          // u ist der Vorgänger
            if (p(u)>=p(v))     // u hat die Heap-Eigenschaft
                return;
            exchange(u, v);
            v=u;                // weiter mit u
        }
    }

    private void downheap()
    {
        int w, v=root();
        while (!isLeaf(v))      // v ist kein Blatt
        {
            w=succ(v);          // erster Nachfolger
            if (exists(w+1))    // gibt es einen zweiten Nachfolger?
                if (p(w+1)>p(w))
                    w++;
             // w ist der Nachfolger mit der größeren Markierung
            if (p(v)>=p(w))     // v hat die Heap-Eigenschaft
                return;
            exchange(v, w);
            v=w;                // weiter mit w
        }
    }

    // liefert den Eintrag v
    private Pair<Double, Type> get(int v)
    {
        return a.get(v);
    }

    // liefert die Priorität des Eintrags v
    private double p(int v)
    {
        return updown*get(v).get0();
    }

    // Einträge an Position i und j vertauschen
    private void exchange(int i, int j)
    {
        Pair<Double, Type> h=a.get(i);
        a.set(i, a.get(j));
        a.set(j, h);
    }

    // Wurzel
    private int root()
    {
        return 0;
    }

    // letztes Blatt
    private int lastLeaf()
    {
        return size()-1;
    }

    // Vorgänger
    private int pred(int v)
    {
        return (v-1)/2;
    }

    // erster Nachfolger
    private int succ(int v)
    {
        return v*2+1;
    }

    // true, wenn v die Wurzel ist
    private boolean isRoot(int v)
    {
        return v==0;
    }

    // true, wenn v ein Blatt ist
    private boolean isLeaf(int v)
    {
        return v>=size()/2;
    }

    // true, wenn v existiert
    private boolean exists(int v)
    {
        return v<size();
    }

    // true, wenn die Liste leer ist
    public boolean isEmpty()
    {
        return a.isEmpty();
    }

    // Länge der Liste
    public int size()
    {
        return a.size();
    }

}    // end class PriorityQueue

import junit.framework.TestCase;

public class TestPriorityQueue extends TestCase
{
    public void testPriorityQueue()
    {
        PriorityQueue<String> pq=new PriorityQueue<String>(-1);
        pq.insert(3, "3");
        pq.insert(5, "5");
        pq.insert(-2, "-2");
        pq.insert(5, "5");
        pq.insert(-2, "-2");
        pq.insert(1, "1");

        System.out.println(pq.extractObj());
        System.out.println(pq.extractObj());
        System.out.println(pq.extractObj());
        System.out.println(pq.extractObj());
        System.out.println(pq.extractObj());
        System.out.println(pq.extractObj());
    }
}

public class Pair<TypA, TypB>
{
    private TypA u;
    private TypB v;

    public Pair(TypA u_, TypB v_)
    {
        u=u_;
        v=v_;
    }

    public TypA get0()
    {
        return u;
    }

    public TypB get1()
    {
        return v;
    }

    public boolean equals(Pair<TypA, TypB> other)
    {
        return get0().equals(other.get0()) && get1().equals(other.get1());
    }

    public String toString()
    {
        return "("+u+", "+v+")";
    }

}