Биномдық қалып: Басымдық кезек құрылымы

Data structure that acts as a priority queue

In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in time, as there are just tree roots to examine. By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to The pointer must be updated when performing any operation other than finding the minimum. This can be done in time per update, without raising the overall asymptotic running time of any operation.

After decreasing the key of an element, it may become smaller than the key of its parent, violating the minimum heap property. If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until the minimum heap property is no longer violated. Each binomial tree has height at most , so this takes time. However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.

To delete an element from the heap, decrease its key to negative infinity (or equivalently, to some value lower than any element in the heap) and then delete the minimum in the heap.