Binomial-Heap

In computer science, a binomial heap is a data structure, specifically a heap, which, like binary heaps, can be used as a priority queue. That is, in any order efficiently elements with fixed-priority can be put into the heap and always the element with the highest priority can be removed.

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

The priority of the items will be impressed by this key. Must therefore be on the set of keys are a total order, as it appears, for example, the less- equal relation ( ≤ ) over the integers.

Binomial Heaps were first described in 1978 by Jean Vuillemin. 1987 derived a new data structure of Michael L. Fredman and Robert Tarjan of it, the so-called Fibonacci heaps. These have recouped some cases better runtimes and see other application in Dijkstra's algorithm and the algorithm of Prim your worst-case running time is partially but 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 - to return and for removing an element with minimum key ( = highest priority)
• CHANGEKEY - to change the key of an element and
• Merge - for merging two heaps.

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

Binomial trees

Binomial Heaps consist of a list of binomial trees of different order. Binomial trees and their order can be recursively defined as follows:

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

A binomial tree of order k can therefore also easily create from two binomial trees of order k - 1 by one of the two trees is made the leftmost child of the other. From this construction it is easy to deduce by mathematical induction with the property that a binomial tree of order k has exactly 2k nodes and the height k.

Structure of a binomial heap

A binomial heap stores its elements and the associated keys in the nodes of its binomial trees. And it also has the following properties:

• Each binomial tree in the heap satisfies the heap condition, that is, except the root, which has no parent node, applies to each of its nodes that the corresponding key is greater than or equal to the key of its parent node.
• For every natural number k at most one binomial tree of order k exists

Ensuring the first characteristic, that the root of each tree carries an element with the smallest key in the tree. Together with the property that a binomial tree of order k has exactly 2k nodes, the second property ensures that the specified exactly for a binomial heap with n elements, how many trees the heap and to define the order have this.

This is determined by the binary representation of n. If the digit numbered starting from right to left as 0, a tree of order k exists if and only if a 1 in the binary representation at the point k. This also means that a heap of n elements at most log2 (n 1) contains binomial trees. A binomial heap with 13 = 11012 elements for example, has exactly one tree of order 3, a tree of order 2 and a tree of order 0

The set of binomial trees is implemented as a sorted ( according to the order of the trees ) list of the roots of these trees. A binomial heap has as opposed to the binary heap is not a single root, but several. These are called root list. Thus, the running time for finding the minimum on O ( log n) increases, since all elements of the root list must be searched.

Implementation of operations

Merging two heaps (merge)

The central operation is the fusion of two heaps (merge), since it is used as a sub- program of 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 of n1 and n2 of the merging heap.

To this end, the lists of the two heaps are simultaneously beginning through to the trees lowest order. A carry, if necessary, detained (in the form of a tree ) - In a special variable is - similar to the bitwise addition. Initially, this transfer is empty.

Now let x be the highest binary digit of different from 0, ie. For every natural number k such that the number of trees with order k will now be considered in two heaps, and in the carry variables in ascending order. If this

• 0, then nothing happens.
• 1, the corresponding tree is transferred to the new heap and, if necessary, emptied the transfer.
• 2, so is the tree whose key is greater at the root, made ​​the leftmost child of another tree and keep the so resulting tree of order k 1 as a carry.
• 3, so the tree is taken from the transfer to the new heap and the two trees in the heap of the tree whose key is greater at the root is made the leftmost child of another tree and so resulting tree of order k 1 retain as a carry.

Each of these steps can be performed in constant time. Since a maximum of such steps are made, the operation requires, in the worst case, only logarithmic time.

Remove an element ( remove)

Besides merge is the removal of an element ( remove), the most demanding operation. Let X be the element to remove his order x and T is the binomial tree that contains this element and its order is k. Starting with X must be the binomial tree that contains the item can be suitably broken up into smaller binomial trees. This splitting of the tree is most easily done with a recursive function split, which is passed as an argument to a node in the tree. Initially X is itself the argument. If the argument passed has a parent node, the function first calls itself with this as an argument and then removes long as the leftmost child of the Father - so the child with the highest order - to the argument itself has been removed from the tree.

Since the removal of the leftmost element is just the inverse operation to the presented above recursive construction of the binomial trees, so the trees and split 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 in exactly two binomial trees of order x and in each case a binomial tree of order x 1, x 2, ..., k - 1 decay. Are now still all children of X removed in the same way, so X is completely isolated and can be safely deleted. Here, from the children for each j in {0, ..., x - 1} occurs exactly one binomial tree of order j. Overall, therefore { k -1 0, ..., } is a binomial tree of order remains for each j from j left. These trees together again a binomial heap, which can be merged using merge with the rest of the heap.

Cleaving the leftmost element is possible in constant time. Since the original tree is exactly k split times, but the binomial heap contains at least 2k elements, this operation requires in the worst case only logarithmic time. Because the final merge is itself only logarithmically requires a lot of time, the total running time in the worst case logarithmic to the number of elements in the heap.

Further operations

The remaining operations make now very easy.

• To insert a new element (insert ), just a new heap is created, containing only this element and this merged using merge with the actual heap.
• To remove an element with minimum key ( extractMin ), only the minimum of the roots need to be found by the list of roots is run once and the found item is removed with remove and returned.
• To change the key of an element ( CHANGEKEY ) will remove this with first removed, then changed the key and then inserted with insert again.

Comments

The operations and remove CHANGEKEY assume that the position of the corresponding elements in the heap is known. In general, it is in fact not possible to efficiently search for an item in the heap. Therefore, the operation must insert return a pointer to the container for the inserted element to the calling program remembers at a suitable location in case of need.

There is an alternative to the implementation shown here. However, this only allows decreasing the key of an element. Accordingly, ie, the operation will not CHANGEKEY but decreasekey. However, the operation decreasekey is implemented directly instead of remove. This exchanges the key from easy, and the heap condition thereby restore that element and keys are exchanged as long as the supporting tanks with which the Father until the heap condition is satisfied again. The operation remove is then implemented so that decreasekey with the key of the element is made ​​quasi- infinitely small, so that the element migrates to the root of his binomial tree. Then the kids can be the new root is removed and inserted again merge into the tree.

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