Teil I - Implementation von Priority Queues

• Aufbauend auf dem Interface zentrale.priorityqueue.PriorityQueue sollen unten aufgeführte Priority Queues implementiert werden. Diese sollen in einer package gruppe.priorityqueue, wobei gruppe den Gruppennamen bezeichnet, zusammengefasst werden. Dazu wird im Projekt der Gruppe (siehe CVS) ein Verzeichnis priorityqueue angelegt und darin Klassen mit den Bezeichnungen, die in der unten aufgeführten Liste angegeben sind, erstellt.
  Als Beispiel geben wir die Implementation einer Linked List Priority Queue vor:

  «zentrale/priorityqueue/UnsortedListPQ.java»

• Diese Priority Queues sollen ausgiebig getestet werden: Eine Test Suite führt für eine beliebige Priority Queue, die das obige Interface implementiert, Operationen in möglichst allen denkbaren und undenkbaren Kombinationen aus, und testet, ob diese korrekt ausgeführt wurden.

Die Priority Queues:

1. Linked List: UnsortedListPQ

[CLR90] Seite 204ff
[OW93] Seite 39ff

2. Sorted Linked List: SortedListPQ

3. d-Heap: HeapPQ

[CLR90] Seite 147ff
[OW93] Seite 114ff, Seite 418ff

4. Links-Baum: LeftistTreePQ

[OW93] Seite 425ff

5. Red-Black Tree: RedBlackTreePQ

[CLR90] Seite 263ff
[Me84] Seite 206ff

6. Binomial Heap: BinomialHeapPQ

[CLR90] Seite 400ff
[OW93] Seite 428ff

7. Fibonacci Heap: FibonacciHeapPQ

[CLR90] Seite 420ff
[OW93] Seite 435ff

8. Weak Heap

9. Bucket Queue