1-Level-Backets

1-Level-Backets bestehen aus:

• einem Array $b[0\dots C+1]$ zur Aufnahme der Buckets. Jedes b_i enthält einen Pointer auf die Liste der Elemente im Buckets,
• einer Zahl minvalue, die gleich dem kleinsten gespeicherten Schlüssel ist,
• einer Zahl $0\leq minpos \leq C$, die den Index des Buckets mit dem kleinsten Schlüssel enthält, und
• einer Zahl n, die die Anzahl der gespeicherten Elementen enthält.

Wie bei jeder Vorrangswarteschlange müssen drei Operationen unterstützt werden:

• Insert(x) : fügt das Element x in die Vorrangswarteschlange ein
• ExtractMin : liefert und löscht das erste Element der Vorrangswarteschlange
• DecreaseKey(x,k) : verringert Schlüssel des Elements x auf den Wert k.

Dazu kommt noch eine Initialisierung Initialize . Für 1-Level-Buckets sehen die Operationen wie folgt aus:

1.

Initialize(x) :

		 $n:=0, minvalue:=\infty$;  		 reserviere Platz für b (C sei bekannt);   

2.

Insert : Füge x in b[Key(x) mod (C+1)] ein

		 n:=n+1;  		 if (Key(x) < minvalue) then
		 co x ist jetzt das Element mit dem kleinsten Schlüssel oc
		 		 minpos := Key(x) mod (C+1);
		 		 minvalue := Key(x);
		 fi   

3.

ExtractMin : Entferne ein beliebiges Element aus b[minpos]

		 n:=n-1;  		 if (n>0) then
		 		 co suche neues Element mit dem kleinsten Schlüssel oc
		 		 while b[minpos] ist leer do
		 		 		 minpos := (minpos +1) mod (C+1) od
		 		 minvalue:= Key eines Elements in b[minpos] ;  		 else $minvalue:= \infty$ ; fi   

4.

DecreaseKey(x,k) : Entferne x aus seinem momentanen Bucket;

		 n:=n-1;  		 Key(x) := k;
		    Insert(x);

Bei geeigneter Implementierung der Buckets, zB. als doppellt verkettete Listen gilt:




Beweis: Wird x am Anfang der Liste eingefügt, so müssen bei Insert nur einige Zeiger umgehängt sowie n, minpos und minvalue angepaßt werden, was wieder nur ein paar Zeigeroperationen sind. Die Aktualisierung von n, minpos und minvalue benötigt auch nur konstante Zeit. Für das Finden des nächstkleinsten Elementes müssen aber möglicherweise alle weiteren Buckets betrachtet werden, im schlimmsten Falle C, da bei DecreaseKey das Element x direkt übergeben wird, sind neben dem Einfügen auch nur wenige Zeigeroperationen und je eine Zuweisung an n und Key(x) nötig. $\Diamond$