Skew heap

from Wikipedia, the free encyclopedia

In computer science, a skew heap (or self-balancing heap) is a heap data structure implemented as a binary tree . Compared to binary heaps, skew heaps can be merged more quickly. However, they have no structural restrictions, which means that the height of the tree, i.e. the largest number of interconnected nodes , is no longer necessarily less than the logarithm of the total number of nodes.

An implementation of a skew heap must meet two conditions:

  • The data to be stored in the skew heap needs order .
  • Any operation on one or two skew heaps (e.g. adding or removing nodes) must be performed by merging the skew heaps.

By means of amortized runtime analysis, it can be shown that all operations on a skew heap can be carried out with an algorithmic complexity of .

definition

Skew heaps can be defined recursively :

  • A heap with only one element is a skew heap.
  • The result of the merging operation (merge) of two skew heaps is also a skew heap.
    • The merge operation is defined.

Operations

Recursive merging of two heaps (recursive merge)

The recursive merging of two skew heaps is similar to the merging of two link sheaps :

  • Let two heaps p and q be given , where the root of p is smaller than that of q . Let the fused tree be r .
  • The root of p becomes the root of r .
  • The left subtree in p becomes the right subtree in r .
  • The right subtree from p is merged recursively with q . The result becomes the left subtree in r
  • The merge is complete when there are no more nodes left in the subtrees.

  • Two skew heaps. The root of the left heap (1) is smaller than that of the right (13).

  • The result of the merger

Non-recursive merging of two heaps (non-recursive merge)

As an alternative to the recursive merging of two skew heaps, there is a non-recursive algorithm which, however, requires sorting before the actual merging.

  • Divide both skew heaps into subtrees by separating the right subtree from the root and making it a separate tree.
  • Repeat step 1 for all separated subtrees until each root of each new tree has only one left subtree. The result is a set of trees that either have a left subtree or no subtree at all.
  • Sort the resulting amount of trees in ascending order according to the keys of the roots.
  • Combine the last two trees of the sorted set (from right to left) according to this rule:
    • If the root of the penultimate tree has a left subtree, make it the right subtree.
    • Put the root of the last tree as the left subtree of the penultimate tree.
  • Repeat the last step until there is only one tree left.

  • initial situation

  • Division and sorting of the skew heaps

  • 1. Combination of the last two trees

  • 2. Combination of the last two trees

  • 3. Combination of the last two trees

  • 4. Combination of the last two trees with swapping of the subtrees

  • 5. Combination and outcome

Add node (add)

Adding a node to an existing skew heap is done by merging. The new node is treated as an independent heap and is merged with the existing one.

Remove node with the lowest value (Remove_min or extract_min)

The root of a skew heap is necessarily the node with the lowest value and can therefore be easily queried. The smallest knot is removed by merging the two resulting subtrees.

implementation

In many functional programming languages , skew heaps can be implemented very easily. The following is an example of an implementation in Haskell. 

data SkewHeap a = Empty
                | Node a (SkewHeap a) (SkewHeap a)

singleton :: Ord a => a -> SkewHeap a
singleton x = Node x Empty Empty

union :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
Empty              `union` t2                 = t2
t1                 `union` Empty              = t1
t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2)
   | x1 <= x2                                 = Node x1 (t2 `union` r1) l1
   | otherwise                                = Node x2 (t1 `union` r2) l2

insert :: Ord a => a -> SkewHeap a -> SkewHeap a
insert x heap = singleton x `union` heap

extractMin :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a)
extractMin Empty        = Nothing
extractMin (Node x l r) = Just (x, l `union` r)

literature

Individual evidence

  1. ^ Daniel Dominic Sleator, Robert Endre Tarjan: Self-Adjusting Heaps . In: SIAM Journal on Computing , 15 (1), 1986, pp. 52-69. doi: 10.1137 / 0215004 , ISSN  0097-5397 .
  2. ↑ Berry Schoenmakers: A Tight Lower Bound for Top-Down Skew Heaps . In Information processing letters , 61, no. 5, March 14, 1997, pp. 279-284, ISSN  0020-0190 .