A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value. The leftist tree was invented by Clark Allan Crane.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- Ein Linksbaum oder Linksheap ist eine Vorrangwarteschlange, die durch eine Variante eines Binärbaumes verwirklicht ist. Diese Datenstruktur ist eine Erfindung von Clark Allan Crane und nutzt eine Heapstruktur. Linksbäume sollen, im Gegensatz zu binären Heaps, sehr unbalanciert sein. Die Kindknoten sind so sortiert, dass der rechte Pfad der kürzere von der Wurzel zu einem Blatt ist. Wenn ein neuer Knoten in einen Baum eingefügt wird, wird ein neuer einknotiger Baum erstellt und mit dem alten Baum verschmolzen. Beim Löschen eines Knotens wird dieser entfernt, und die beiden Unterknoten werden mit dem alten Baum verschmolzen. Beide Operationen benötigen logarithmische Zeit: O(log n). Einfügungen sind langsamer als bei binären Heaps, die in amortisierten Laufzeitanalysen eine konstante Zeit benötigen: O(1). Der Vorteil von Linksbäumen besteht in ihrer Fähigkeit, schnell verschmolzen zu werden, verglichen mit binären Heaps, die dafür eine Komplexität von Θ(n) haben. Jedoch benötigen Skew Heaps meist weniger Rechenzeit.
- A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value. The leftist tree was invented by Clark Allan Crane. The name comes from the fact that the left subtree is usually taller than the right subtree. When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete a minimum item, we remove the root and the left and right sub-trees are then merged. Both these operations take O(log n) time. For insertions, this is slower than binary heaps which support insertion in amortized constant time, O(1) and O(log n) worst-case. Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n). In almost all cases, skew heaps have better performance.
|
| dbpedia-owl:thumbnail
| |
| dbpedia-owl:wikiPageExternalLink
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Ein Linksbaum oder Linksheap ist eine Vorrangwarteschlange, die durch eine Variante eines Binärbaumes verwirklicht ist. Diese Datenstruktur ist eine Erfindung von Clark Allan Crane und nutzt eine Heapstruktur. Linksbäume sollen, im Gegensatz zu binären Heaps, sehr unbalanciert sein. Die Kindknoten sind so sortiert, dass der rechte Pfad der kürzere von der Wurzel zu einem Blatt ist.
- A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value. The leftist tree was invented by Clark Allan Crane.
|
| rdfs:label
| |
| owl:sameAs
| |
| foaf:depiction
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
