Class Heap

java.lang.Object
  extended byjava.util.AbstractCollection
      extended byjava.util.AbstractList
          extended byjava.util.Vector
              extended byHeap
All Implemented Interfaces:
java.lang.Cloneable, java.util.Collection, java.util.List, java.util.RandomAccess, java.io.Serializable

public class Heap
extends java.util.Vector

Einfache Implementierung eines Heaps (Prioritätswarteschlange) mittels Vectoren. Für die geringe Anzahl an Knoten und Kanten wird diese Implementation schnell genug sein, um mittels Dijkstra einen kürzesten Weg zu ermitteln. Reicht diese Implementierung nicht aus, dann kann z.B. auf Skiplisten, oder Fibonacci Heaps zurückgegriffen werden. Zu Skiplisten gibt es im Internet die ein oder andere Implementation (z.B. bei http://iamwww.unibe.ch/~wenger). Der Heap wird nur in der Routine getMin(), bzw. findAndRemoveMin() sortiert, damit das Element mit dem kleinsten Schlüssel zurückgegeben werden kann. Wird diese Methode nicht benutzt, dann kann der Heap auch als einfache Warteschlange benutzt werden.

See Also:
Serialized Form

Field Summary
 
Fields inherited from class java.util.Vector
capacityIncrement, elementCount, elementData
 
Fields inherited from class java.util.AbstractList
modCount
 
Constructor Summary
Heap()
           
 
Method Summary
 void add(HeapElement he)
          Hinzufügen eine HeapElements.
 void addOrReplace(HeapElement hel)
          Fügt ein Element in den Heap ein.
 boolean contains(HeapElement he)
          Prüft, ob ein Element in dem Heap enthalten ist.
 void decreaseKey(HeapElement he, int new_key)
          ändert den Schlüssel des Elements he.
 HeapElement find(Node n)
          Das Element mit dem Knoten n wird gesucht und wenn es gefunden wird zurückgegeben.
 HeapElement findAndRemoveFirstElement()
          holt das erste Element und löscht es aus dem Heap.
 HeapElement findAndRemoveMin()
          Sucht das Minimum und löscht es aus dem Heap.
 HeapElement findMin()
          Suchen und zurückgeben des Elements mit dem kleinsten Schlüssel.
 int getCost(Node n)
          Ermittel die Kosten eines Elements mit dem Knoten n.
 HeapElement getMin()
          Gibt das Minimum aus dem Heap zurück.
 void remove(HeapElement he)
          Löscht das HeapElement, wenn es in dem Heap enthalten ist.
 void setCost(Node n, int cost)
          Setze die Kosten für das Element mit dem Knoten n auf cost.
 
Methods inherited from class java.util.Vector
add, add, addAll, addAll, addElement, capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, get, hashCode, indexOf, indexOf, insertElementAt, isEmpty, lastElement, lastIndexOf, lastIndexOf, remove, remove, removeAll, removeAllElements, removeElement, removeElementAt, removeRange, retainAll, set, setElementAt, setSize, size, subList, toArray, toArray, toString, trimToSize
 
Methods inherited from class java.util.AbstractList
iterator, listIterator, listIterator
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.List
iterator, listIterator, listIterator
 

Constructor Detail

Heap

public Heap()
Method Detail

add

public void add(HeapElement he)
Hinzufügen eine HeapElements. Dieses wird intern in ein Object gecastet und im Heap eingefügt.


addOrReplace

public void addOrReplace(HeapElement hel)
Fügt ein Element in den Heap ein. Kommt das Element in dem Heap schon vor, so wird das schon enthaltende Element gelöscht und das neue Element eingefügt.


remove

public void remove(HeapElement he)
Löscht das HeapElement, wenn es in dem Heap enthalten ist.


findAndRemoveMin

public HeapElement findAndRemoveMin()
Sucht das Minimum und löscht es aus dem Heap. Das Minimum, also das Element mit dem kleinsten Schlüssel (HeapElement muss also das Interface Comparable implementieren) wird anschliessend aus dem Heap gelöscht.


findAndRemoveFirstElement

public HeapElement findAndRemoveFirstElement()
holt das erste Element und löscht es aus dem Heap. Dabei ist der Wert des Elements egal.


contains

public boolean contains(HeapElement he)
Prüft, ob ein Element in dem Heap enthalten ist.


getMin

public HeapElement getMin()
Gibt das Minimum aus dem Heap zurück. Dabei wird der Heap zunächst sortiert, damit das Element mit dem kleinsten Schlüssel an erster Stelle steht.


findMin

public HeapElement findMin()
Suchen und zurückgeben des Elements mit dem kleinsten Schlüssel.


decreaseKey

public void decreaseKey(HeapElement he,
                        int new_key)
ändert den Schlüssel des Elements he. Dabei wird das Element he aus dem Heap gelöscht, der neue Schlüssel von he gesetzt und anschliessend in dem Heap eingefügt.


find

public HeapElement find(Node n)
Das Element mit dem Knoten n wird gesucht und wenn es gefunden wird zurückgegeben. Wird es nicht gefunden, dann wird ein initialisiertes HeapElement zurückgegeben.


getCost

public int getCost(Node n)
Ermittel die Kosten eines Elements mit dem Knoten n.


setCost

public void setCost(Node n,
                    int cost)
Setze die Kosten für das Element mit dem Knoten n auf cost.