Basisklassen

Klasse PriorityQueue

 aufwärts

Die Klasse PriorityQueue implementiert eine Prioritäten­liste. PriorityQueue speichert Paare (Zahlenwert, Objekt), die mit der Funktion insert eingegeben werden. Mit der Funktion extract wird jeweils das Paar mit dem höchsten Zahlenwert zurück­gegeben und aus der Liste gelöscht.

Die Prioritäten­liste ist als binärer Baum mit der Eigenschaft eines Heaps organisiert. Sowohl insert als auch extract benötigen O(log(n)) Schritte, wobei n die Anzahl der Einträge in der Prioritäten­liste ist.

Beim Aufruf des Konstruktors wird mit dem Parameter updown = 1 oder updown = -1 festgelegt, ob mit extract das Paar mit dem höchsten oder mit dem niedrigsten Zahlenwert zurück­gegeben werden soll.

 

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

 

Mit folgendem Testprogramm lässt sich die Klasse PriorityQueue vom Typ -1 testen.

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());
    }
}

 

Die Klasse PriorityQueue verwendet Objekte vom Typ Pair zur Speicherung der Paare (Zahlenwert, Objekt).

 

public class Pair<Type0, Type1>
{
    private Type0 u;
    private Type1 v;

    public Pair(Type0 u_, Type1 v_)
    {
        u=u_;
        v=v_;
    }

    public Type0 get0()
    {
        return u;
    }

    public Type1 get1()
    {
        return v;
    }

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

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

}

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 06.02.2009   Updated: 17.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik