Leftist tree

A left tree or Linksheap is a binary tree that can be used as a priority queue. This data structure is an invention of Clark Allan Crane and uses a heap structure. Links trees do not demand as opposed to balanced Binarbäumen that each path has at most logarithmic length. It is sufficient that there is a node of each logarithmic long path to a sheet and the latter is known. Links trees can be efficiently Fused.

Definition

Left tree is defined over a set of totally ordered keys. The defined keys on the order determines the priority of a key.

  • A node with distance 0 and a minimal key priority is a left tree.
  • A node with two links trees as children is a left tree if: His key at least as high priority as the key to his children ( heap property ).
  • Its distance by exactly 1 is greater than the distance of the right child.

The definition implies that the distance measuring the length of the shortest path to a sheet. If you follow links in a tree always the right child, so you go such a shortest path.

Operations

Left tree with n keys supports the following operations guaranteed in O ( log n) time:

  • Insert - to insert an element
  • ExtractMin - to return and for the removal of an element with the highest priority and
  • Merge - for merging two heaps.

Algorithms

Note that here a node with distance 0 represents an empty tree links. In one implementation, such usually is represented as a null pointer.

Merging (merge)

This operation is two links trees into a new tree fusing links.

Let K be the tree with smaller priority and G the tree with greater priority ( they have the same priority decide arbitrarily ). The method may then recursively be described as follows:

The steps ensure successively the properties have been required in the definition of the resulting tree links.

Paste ( insert)

To insert a new key create a new node with the desired keys and merge the newly created links to tree with the old tree. The newly created node should have two links trees with distance 0 as children before fusing.

Extracting of the next element ( extractMin )

Because the heap property is the key with the highest priority in each case at the root and so it can be read directly. The children of the root are merged and set the result as the new root. This operation is valid only if the root has at least distance 1.

Term

  • The merging of two links trees with a total of n nodes by means of merge requires O (log n) time:

In each step of the recursion much work is done constantly. Each recursive call is made on trees whose distances are shorter in total by exactly one. The recursion keep the latest when the sum of the distances is one. So the running time is bounded by the sum of the distances. Since the distances for defining the length of the links trees shortest path, identified and the length of the shortest path in a binary tree with nodes k at most log 2 ( k) 1, followed by the barrier.

  • The running time for insert and extractMin is bounded by a constant plus the time to merge two links trees.
514387
de