In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. 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 height-biased leftist tree was invented by . The name comes from the fact that the left subtree is usually taller than the right subtree.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Linksbaum (de)
- Leftist tree (en)
- 左偏树 (zh)
|
| rdfs:comment
| - Ein Linksbaum oder Linksheap ist ein Binärbaum, der als Vorrangwarteschlange benutzt werden kann. Diese Datenstruktur ist eine Erfindung von 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. (de)
- 左偏树（英语：leftist tree或leftist heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。 不同于斜堆合并的,左偏堆的合并操作的为O(log n)，而完全二叉堆为O(n)，所以左偏堆适合基于合并操作的情形。 由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。 (zh)
- In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. 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 height-biased leftist tree was invented by . The name comes from the fact that the left subtree is usually taller than the right subtree. (en)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Ein Linksbaum oder Linksheap ist ein Binärbaum, der als Vorrangwarteschlange benutzt werden kann. Diese Datenstruktur ist eine Erfindung von 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. (de)
- In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. 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 height-biased leftist tree was invented by . The name comes from the fact that the left subtree is usually taller than the right subtree. A leftist tree is a mergeable heap. When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete an item, it is replaced by the merge of its left and right sub-trees. Both these operations take O(log n) time. For insertions, this is slower than Fibonacci heaps, which support insertion in O(1) (constant) amortized time, 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, the merging of skew heaps has better performance. However merging leftist heaps has worst-case O(log n) complexity while merging skew heaps has only amortized O(log n) complexity. (en)
- 左偏树（英语：leftist tree或leftist heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。 不同于斜堆合并的,左偏堆的合并操作的为O(log n)，而完全二叉堆为O(n)，所以左偏堆适合基于合并操作的情形。 由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
