Binomial heap

In computer science , a binomial heap is a data structure , more precisely a heap , which, like binary heaps , can be used as a priority queue . This means that elements with a defined priority can be efficiently placed in the heap in any order and the element with the highest priority can always be removed.

In contrast to binary heaps, binomial heaps can also be combined efficiently. This allows, for example, effectively in a multi-processor multitasking - system the tasks of an overloaded processor to transmit another.

The priority of the elements is imprinted on them by keys . There must therefore be a total order over the set of keys, for example the less than or equal relation (≤) over the whole numbers .

Binomial heaps were first described by Jean Vuillemin in 1978 . In 1987 Michael L. Fredman and Robert Tarjan derived a new data structure from this, the so-called Fibonacci heaps . These have recouped some better times and find, among other applications in Dijkstra's algorithm and Prim's algorithm . However, their worst-case runtime is sometimes significantly worse, which is why they are not suitable for online algorithms .

Operations

Binomial heaps efficiently support the operations

insert - to insert an element,
remove - to remove an element,
extractMin - for returning and removing an element with a minimum key (= highest priority),
changeKey - to change the key of an element and
merge - to merge two heaps.

All operations can be implemented with a worst-case runtime of O (log n ), where n is the number of elements currently in the heap.

Binomial trees

Binomial tree of order 3

Binomial heaps consist of a list of binomial trees of various orders. Binomial trees and their order are recursively defined as follows :

A binomial tree of order 0 consists of a single node .
A binomial tree of order k has a root with degree k, whose children exactly the order k -1, k -2, ..., have (in that order) 0th

A binomial tree of order k can also easily be created from two binomial trees of order k −1 by making one of the two trees the leftmost child of the other. From this construction one can easily derive the property by complete induction that a binomial tree of order k has exactly 2 ^k nodes and height k .

Structure of a binomial heap

A binomial heap stores its elements and the associated keys in the nodes of its binomial trees. It fulfills the following properties:

Every binomial tree in the heap fulfills the heap condition, that is, with the exception of the root, which has no parent node , it applies to each of its nodes that the associated key is greater than or equal to the key of its parent node.
For every natural number k there is at most one binomial tree of order k .

Example of a binomial heap with 13 elements. The keys of the fathers are at most as big as the keys of their children.

The first property ensures that the root of every tree carries an element with the smallest key in the tree. Together with the property that a binomial tree of order k has exactly 2 ^k nodes, the second property ensures that for a binomial heap with n elements it is exactly specified how many trees the heap has and what order they have.

This is determined by the binary representation of n . If the digits are numbered consecutively from right to left with 0, then a tree of order k exists if and only if there is a 1 at k in the binary representation . This also means that a heap with n elements contains at most log ₂ ( n +1) binomial trees. For example, a binomial heap with 13 = 1101 ₂ elements has exactly one tree of order 3, one tree of order 2 and one tree of order 0.

The set of binomial trees is implemented as a list of the roots of these trees sorted (according to the order of the trees) . In contrast to the binary heap, a binomial heap does not have a single root, but several. These are called the root list . This increases the runtime for finding the minimum to O (log n ), since all elements of the root list must be searched.

Implementation of the operations

Merging two heaps (merge)

Merging two binomial trees of degree 2: Compare the roots and add the other tree (black) as the left subtree to the tree with the smaller root (gray). In the end you get the lower tree with degree 3.

The central operation is the fusion of two heaps (merge) , as these are considered subroutine is used all other operations. The operation is similar to the bitwise addition of binary numbers . In this case, this corresponds to the addition of the number of elements n ₁ and n _{2 of} the heaps to be merged.

For this purpose, the lists of the two heaps are run through simultaneously starting with the trees of the lowest order. A carry (in the form of a tree) is recorded in a special variable - similar to bitwise addition. This carry is initially empty.

Now let x be the highest binary digit different from 0, that is . For each natural number k with , the number of trees with order k in both heaps and in the carry variable is considered in ascending order . Is this ${\ displaystyle n_ {1} + n_ {2}}$ ${\ displaystyle x = \ log _ {2} (n_ {1} + n_ {2} +1) -1}$ ${\ displaystyle 0 \ leq k \ leq x}$

0, nothing happens like this.
1, the corresponding tree is transferred to the new heap and the carryover is emptied if necessary.
2, the tree whose key is larger at the root is made the leftmost child of the other tree and the resulting tree of order k +1 is kept as a carryover.
3, the tree from the carryover is taken over into the new heap and the tree whose key is larger at the root of the two trees in the heaps is made the leftmost child of the other tree and the resulting tree of order Keep k +1 as a carry.

Each of these steps can be carried out in constant time. Since a maximum of such steps are taken, the operation only takes a long logarithmic time in the worst case . ${\ displaystyle \ log _ {2} (n_ {1} + n_ {2} +1)}$

Removing an element (remove)

Splitting a binomial tree using split . Triangles symbolize the new subtrees. The labeling of the nodes indicates their order before or after splitting. We have k > a ₁ > a ₂ > ...> a _i = x , where i +1 is the depth of node X in the tree.

In addition to merge the removal of an element (remove) the most demanding operation. Let X be the element to be removed, its order x and T the binomial tree that contains this element and whose order is k . Starting from X , the binomial tree that contains the element must be appropriately split into smaller binomial trees. The easiest way to split the tree is to use a recursive function split , which is passed as an argument to a node in the tree. Initially, X itself is the argument. If the passed argument has a parent node, the function first calls itself with this as an argument and then removes the leftmost child of the father - i.e. the child with the highest order - until the argument itself has been removed from the tree.

Since the removal of the element furthest to the left represents the opposite operation to the recursive structure of the binomial trees shown above, the trees split off in this way and the rest are still binomial trees. Furthermore, X is now the root of a tree and it can be shown that the original tree is now divided into exactly 2 binomial trees of the order x and one binomial tree each of the order x +1, x +2, ..., k- 1 has disintegrated. If all children are removed from X in the same way , X is completely isolated and can be deleted without any problems. The children for each j in {0, ..., x -1} result in exactly one binomial tree of order j . All in all, a binomial tree of order j remains for every j from {0, ..., k -1} . These trees together again form a binomial heap, which can be merged with the rest of the heap using merge .

The leftmost element can be split off in constant time. Since the original tree is split exactly k times, but the binomial heap contains at least 2 ^k elements, this operation only takes a logarithmic amount of time in the worst case. Since the subsequent merge itself only takes a logarithmic amount of time, the total runtime in the worst case is logarithmic to the number of elements in the heap.

Further operations

The other operations are now very easy.

To insert a new element (insert) , a new heap is simply generated, only it contains an element, and this means merge fused to the actual heap.

To extract an element with a minimal key (extractMin) , only the minimum of the roots needs to be found by going through the list of roots once and removing the element found with remove and returning it.

To change the key of an element (changeKey) , it is first removed with remove , then its key is changed and then inserted again with insert .

Remarks

The remove and changeKey operations require that the position of the corresponding elements in the heap is known. In general, it is not possible to find an element in the heap efficiently. The insert operation must therefore return a pointer to the container for the inserted element, which the calling program remembers in a suitable place if necessary.

There is an alternative to the implementation shown here. However, this only allows the key of an element to be reduced. Accordingly, the operation is then not called changeKey , but decreaseKey . Instead of remove, the decreaseKey operation is implemented directly. This simply exchanges the key and restores the heap condition by exchanging the element and key in the carrying containers with those of the father until the heap condition is met again. The remove operation is then implemented in such a way that with decreaseKey the key of the element is made almost infinitely small, so that the element moves to the root of its binomial tree. Then the children of the new root can be removed and merge be reinserted into the tree.

The problem with this method is that after a decreaseKey, the assignment of the elements to their containers is no longer correct. The changes have to be communicated to the calling program somehow.

literature

Thomas H Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . Oldenbourg, Munich, Vienna 2004, ISBN 3-486-27515-1 (Original title: Introduction to algorithms . Translated by Karen Lippert, Micaela Krieger-Hauwede).
Jean Vuillemin: A data structure for manipulating priority queues . Communications of the ACM 21 , 1978, pp. 309-314.

Web links

This version was added to the list of articles worth reading on August 18, 2005 .