Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
se:algorithmendatenstrukturen [2009-01-17 20:32] stefan |
se:algorithmendatenstrukturen [2009-01-17 20:35] stefan |
||
---|---|---|---|
Zeile 82: | Zeile 82: | ||
* Vorgänger des i. Knotens: i/2 (i >> 1) | * Vorgänger des i. Knotens: i/2 (i >> 1) | ||
* linker Nachfolger des i. Knotens: 2i (i << 1) | * linker Nachfolger des i. Knotens: 2i (i << 1) | ||
- | * rechter Nachfolger des i. Knotens: 2i + 1 ((i << 1) + 1) | + | * rechter Nachfolger des i. Knotens: 2i + 1 ( (i << 1) + 1) |
* Heap (= Binärbaum) mit n Knoten hat Höhe lg n, also können alle Operationen auf einem Heap mit O(lg n) durchgeführt werden | * Heap (= Binärbaum) mit n Knoten hat Höhe lg n, also können alle Operationen auf einem Heap mit O(lg n) durchgeführt werden | ||
* Max-Heap: Nachfolger-Knoten haben kleinere Werte, Min-Heap: Nachfolger-Knoten haben größere Werte | * Max-Heap: Nachfolger-Knoten haben kleinere Werte, Min-Heap: Nachfolger-Knoten haben größere Werte |