Prioritätenliste

Klasse PriorityQueue (als sortierte Liste)

 aufwärts

Die Prioritäten­liste ist hier der Einfachheit halber als sortierte Liste implementiert. Die Liste wird jeweils neu sortiert, bevor ein Element mit extract ausgegeben wird, nachdem vorher Elemente mit insert eingefügt worden sind. Im schlechtesten Fall benötigt extract daher Θ(n log(n)) Schritte, wobei n die Länge der Liste ist; insert benötigt O(1) Schritte.

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.

 

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

}
?>

 

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