|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractCollection
java.util.AbstractList
java.util.Vector
Heap
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.
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 |
public Heap()
Method Detail |
public void add(HeapElement he)
public void addOrReplace(HeapElement hel)
public void remove(HeapElement he)
public HeapElement findAndRemoveMin()
public HeapElement findAndRemoveFirstElement()
public boolean contains(HeapElement he)
public HeapElement getMin()
public HeapElement findMin()
public void decreaseKey(HeapElement he, int new_key)
public HeapElement find(Node n)
public int getCost(Node n)
public void setCost(Node n, int cost)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |