http://update.proggen.org/ 2026-04-19T13:20:45+0200 http://update.proggen.org/ http://update.proggen.org/lib/tpl/proggenY/images/favicon.ico text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=user:glocke:struct:binomial_heap&rev=1663868366 Binomial-Heaps Auch Binomial-Heaps können zur Implementierung einer Priority-Queue verwendet werden. Dabei handelt es sich um eine Menge von Bäumen, die gewöhnlich Min-Heap-geordnet sind. Diese Heaps sind Binomial-Bäume, wobei von jedem Grad höchstens ein Binomial-Baum im Binomial-Heap existiert. Ein Binomial-Baum von Grad <m>k</m> wird mit <m>B_k</m> bezeichnet. text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=user:glocke:struct:fheap&rev=1663868366 Fibonacci-Heap Fibonacci-Heaps sind ungeordnete Mengen von Min-Heaps bei denen Knoten markiert werden können. Im Gegensatz zu Binomial-Heaps sind Fibonacci-Heaps „faule“ Datenstukturen. In sie wird direkt eingefügt ohne Aufzuräumen. Dadurch sind bestimmte Operationen ins konstanter Zeit realisierbar. Aufgeräumt (besser: sortiert) wird, sobald das Minimum entfernt werden soll. text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=user:glocke:struct:minheap&rev=1663868366 Min-Heap Ein Min-Heap ist ein spezieller Heap bei dem rekursiv für jeden Knoten node folgende Heap-Bedingung gilt: Der Wert des Schlüssels des Vaters ist stets kleiner als der Wert des eigenen Schlüssels. Analog existieren Max-Heaps, bei denen analog der Wert des Vaters größer ist als der eigene Wert. Formal kann man für Min-Heaps die Bedingung text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=user:glocke:struct:rbtree&rev=1663868366 Rot-Schwarz-Baum Ein Rot-Schwarz-Baum ist ein spezieller binärer Suchbaum, der automatisch ausbalanciert ist. Dadurch wird gewährleistet, dass er bei n Elementen maximal Höhe ld(n) hat. Dies wird erreicht, in dem die Struktur Binärbaum um folgende Eigenschaften beziehungsweise Regel erweitert wird: