Ein Linksbaum oder Linksheap ist ein Binärbaum, der als Vorrangwarteschlange benutzt werden kann. Diese Datenstruktur ist eine Erfindung von Clark Allan Crane und nutzt eine Heapstruktur. Linksbäume fordern im Gegensatz zu balancierten Binärbäumen nicht, dass jeder Pfad höchstens logarithmische Länge hat. Es genügt, dass es von jedem Knoten einen logarithmisch langen Pfad zu einem Blatt gibt und dieser bekannt ist. Linksbäume können effizient verschmolzen werden.
Ein Linksbaum ist definiert über eine Menge von total geordneten Schlüsseln. Die auf den Schlüsseln definierte Ordnung bestimmt die Priorität eines Schlüssels.
Die Definition impliziert, dass die Distanz die Länge des kürzesten Pfades zu einem Blatt misst. Folgt man in einem Linksbaum immer dem rechten Kind, so geht man einen solchen kürzesten Pfad.
Ein Linksbaum mit n Schlüsseln unterstützt die folgenden Operationen garantiert in O(log n ) Zeit:
Merke, dass hier ein Knoten mit Distanz 0 einen leeren Linksbaum darstellt. In einer Implementierung wird ein solcher für gewöhnlich als null-Zeiger dargestellt.
Diese Operation soll zwei Linksbäume zu einem neuen Linksbaum verschmelzen.
Sei K der Baum mit kleinerer Priorität und G der Baum mit größerer Priorität (haben sie die gleiche Priorität entscheide beliebig). Das Verfahren kann dann rekursiv wie folgt beschrieben werden:
Die Schritte garantieren nacheinander die Eigenschaften die in der Definition verlangt wurden für den resultierenden Linksbaum.
Um einen neuen Schlüssel einzufügen, schaffe einen neuen Knoten mit dem gewünschten Schlüssel und verschmelze den so neu entstandenen Linksbaum mit dem alten Baum. Der neu geschaffene Knoten soll vor dem verschmelzen zwei Linksbäume mit Distanz 0 als Kinder haben.
Wegen der Heap-Eigenschaft ist der Schlüssel mit höchster Priorität jeweils an der Wurzel und er kann also direkt abgelesen werden. Die Kinder der Wurzel werden verschmolzen und das Resultat als neue Wurzel gesetzt. Diese Operation ist nur gültig, falls die Wurzel mindestens Distanz 1 hat.
In jedem Schritt der Rekursion wird konstant viel Arbeit verrichtet. Jeder rekursive Aufruf erfolgt auf Bäumen, deren Distanzen in der Summe um genau eins kürzer sind. Die Rekursion endet spätestens wenn die Summe der Distanzen eins ist. Also ist die Laufzeit beschränkt durch die Summe der Distanzen. Da die Distanzen wegen der Definition von Linksbäumen die Länge des kürzesten Pfades bezeichnen, und die Länge des kürzesten Pfades in einem binären Baum mit k Knoten höchstens log 2 (k) + 1 ist, folgt die Schranke.