Prioritätenliste

<?php
class PriorityQueue
{
    private $a;       // Array
    private $updown;   // extract liefert Maximum (+1) oder Minimum (-1)

    // Konstruktor
    public function PriorityQueue($updown=1)
    {
        $this->a=array();
        $this->updown=$updown;
    }
   
    // Objekt x mit Priorität p einfügen
    public function insert($p, $x=null)
    {
        $this->a[]=array($p, $x);    // an Array anhängen
        $this->upheap();
    }

    // Eintrag maximaler Priorität zurückgeben und löschen
    public function extract()
    {
        $this->exchange($this->root(), $this->lastLeaf());
        $z=array_pop($this->a);
        $this->downheap();
        return $z;
    }

    // maximale Priorität zurückgeben und Eintrag löschen
    public function extractVal()
    {
        $z=$this->extract();
        return $z[0];
    }

    // Objekt maximaler Priorität zurückgeben und Eintrag löschen
    public function extractObj()
    {
        $z=$this->extract();
        return $z[1];
    }

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

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

    // liefert die Priorität des Eintrags v
    private function p($v)
    {
        return $this->updown*$this->a[$v][0];
    }
 
    // Einträge an Position i und j vertauschen
    private function exchange($i, $j)
    {
        $h=$this->a[$i];
        $this->a[$i]=$this->a[$j];
        $this->a[$j]=$h;
    }

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

    // letztes Blatt
    private function lastLeaf()
    {
        return $this->size()-1;
    }

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

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

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

    // true, wenn v ein Blatt ist
    private function isLeaf($v)
    {
        return $v>=floor($this->size()/2);
    }

    // true, wenn v existiert
    private function exists($v)
    {
        return $v<$this->size();
    }

    // true, wenn die Liste leer ist
    public function isEmpty()
    {
        return $this->size()==0;
    }

    // Länge der Liste
    public function size()
    {
        return count($this->a);
    }

}
?>