Prioritätenliste

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

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

    // Eintrag maximaler Priorität zurückgeben und löschen
    public function extract()
    {
        if (!$this->sorted)
        {
            if ($this->updown==1)
                sort($this->a);
            else
                rsort($this->a);
            $this->sorted=true;
        }
        return array_pop($this->a);
    }

    // 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];
    }

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

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

}
?>