Binomial heap

(Redirected from Binomial Tree)

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.[1] Binomial heaps were invented in 1978 by Jean Vuillemin.[1][2]

Binomial heap
Typeheap
Invented1978
Invented byJean Vuillemin
Complexities in big O notation
Space complexity
Time complexity
Function Amortized Worst Case
Insert Θ(1) O(log n)
Find-min Θ(1) O(1)
Delete-min Θ(log n) O(log n)
Decrease-key Θ(log n) O(log n)
Merge Θ(log n) O(log n)

Binomial heap

edit

A binomial heap is implemented as a set of binomial trees (compare with a binary heap, which has a shape of a single binary tree), which are defined recursively as follows:[1]

  • A binomial tree of order 0 is a single node
  • A binomial tree of order   has a root node whose children are roots of binomial trees of orders  ,  , ..., 2, 1, 0 (in this order).
 
Binomial trees of order 0 to 3: Each tree has a root node with subtrees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.

A binomial tree of order   has   nodes, and height  . The name comes from the shape: a binomial tree of order   has   nodes at depth  , a binomial coefficient. Because of its structure, a binomial tree of order   can be constructed from two trees of order   by attaching one of them as the leftmost child of the root of the other tree. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.[1][3]

Structure of a binomial heap

edit

A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:[1]

  • Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent.
  • There can be at most one binomial tree for each order, including zero order.

The first property ensures that the root of each binomial tree contains the smallest key in the tree. It follows that the smallest key in the entire heap is one of the roots.[1]

The second property implies that a binomial heap with   nodes consists of at most   binomial trees, where   is the binary logarithm. The number and orders of these trees are uniquely determined by the number of nodes  : there is one binomial tree for each nonzero bit in the binary representation of the number  . For example, the decimal number 13 is 1101 in binary,  , and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below).[1][3]

 
Example of a binomial heap containing 13 nodes with distinct keys. The heap consists of three binomial trees with orders 0, 2, and 3.

The number of different ways that   items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of  . For   these numbers are

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (sequence A049606 in the OEIS)

If the   items are inserted into a binomial heap in a uniformly random order, each of these arrangements is equally likely.[3]

Implementation

edit

Because no operation requires random access to the root nodes of the binomial trees, the roots of the binomial trees can be stored in a linked list, ordered by increasing order of the tree. Because the number of children for each node is variable, it does not work well for each node to have separate links to each of its children, as would be common in a binary tree; instead, it is possible to implement this tree using links from each node to its highest-order child in the tree, and to its sibling of the next smaller order than it. These sibling pointers can be interpreted as the next pointers in a linked list of the children of each node, but with the opposite order from the linked list of roots: from largest to smallest order, rather than vice versa. This representation allows two trees of the same order to be linked together, making a tree of the next larger order, in constant time.[1][3]

Merge

edit
 
To merge two binomial trees of the same order, first compare the root key. Since 7>3, the black tree on the left (with root node 7) is attached to the grey tree on the right (with root node 3) as a subtree. The result is a tree of order 3.

The operation of merging two heaps is used as a subroutine in most other operations. A basic subroutine within this procedure merges pairs of binomial trees of the same order. This may be done by comparing the keys at the roots of the two trees (the smallest keys in both trees). The root node with the larger key is made into a child of the root node with the smaller key, increasing its order by one:[1][3]

function mergeTree(p, q)
    if p.root.key <= q.root.key
        return p.addSubTree(q)
    else
        return q.addSubTree(p)
 
This shows the merger of two binomial heaps. This is accomplished by merging two binomial trees of the same order one by one. If the resulting merged tree has the same order as one binomial tree in one of the two heaps, then those two are merged again.

To merge two heaps more generally, the lists of roots of both heaps are traversed simultaneously in a manner similar to that of the merge algorithm, in a sequence from smaller orders of trees to larger orders. When only one of the two heaps being merged contains a tree of order  , this tree is moved to the output heap. When both of the two heaps contain a tree of order  , the two trees are merged to one tree of order   so that the minimum-heap property is satisfied. It may later become necessary to merge this tree with some other tree of order   in one of the two input heaps. In the course of the algorithm, it will examine at most three trees of any order, two from the two heaps we merge and one composed of two smaller trees.[1][3]

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())
        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())
        heap.addTree(tree)
        heap.next(); p.next(); q.next()

Because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the sizes of the two heaps, from right-to-left. Whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.[1][3]

Each binomial tree's traversal during merge only involves roots, hence making the time taken at most order   and therefore the running time is  .[1][3]

Insert

edit

Inserting a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Because of the merge, a single insertion takes time  . However, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. With this speedup, across a series of   consecutive insertions, the total time for the insertions is  . Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive insert has an amortized time of   (i.e. constant) per insertion.[1][3]

A variant of the binomial heap, the skew binomial heap, achieves constant worst case insertion time by using forests whose tree sizes are based on the skew binary number system rather than on the binary number system.[4]

Find minimum

edit

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.[1]

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.[citation needed]

Delete minimum

edit

To delete the minimum element from the heap, first find this element, remove it from the root of its binomial tree, and obtain a list of its child subtrees (which are each themselves binomial trees, of distinct orders). Transform this list of subtrees into a separate binomial heap by reordering them from smallest to largest order. Then merge this heap with the original heap. Since each root has at most   children, creating this new heap takes time  . Merging heaps takes time  , so the entire delete minimum operation takes time  .[1]

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min.root then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

Decrease key

edit

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.[1] 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.[3]

Delete

edit

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.[1]

Summary of running times

edit

Here are time complexities[5] of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.

Operation find-min delete-min decrease-key insert meld make-heap[a]
Binary[5] Θ(1) Θ(log n) Θ(log n) Θ(log n) Θ(n) Θ(n)
Skew[6] Θ(1) O(log n) am. O(log n) am. O(log n) am. O(log n) am. Θ(n) am.
Leftist[7] Θ(1) Θ(log n) Θ(log n) Θ(log n) Θ(log n) Θ(n)
Binomial[5][9] Θ(1) Θ(log n) Θ(log n) Θ(1) am. Θ(log n)[b] Θ(n)
Skew binomial[10] Θ(1) Θ(log n) Θ(log n) Θ(1) Θ(log n)[b] Θ(n)
2–3 heap[12] Θ(1) O(log n) am. Θ(1) Θ(1) am. O(log n)[b] Θ(n)
Bottom-up skew[6] Θ(1) O(log n) am. O(log n) am. Θ(1) am. Θ(1) am. Θ(n) am.
Pairing[13] Θ(1) O(log n) am. o(log n) am.[c] Θ(1) Θ(1) Θ(n)
Rank-pairing[16] Θ(1) O(log n) am. Θ(1) am. Θ(1) Θ(1) Θ(n)
Fibonacci[5][17] Θ(1) O(log n) am. Θ(1) am. Θ(1) Θ(1) Θ(n)
Strict Fibonacci[18][d] Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(n)
Brodal[19][d] Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(n)[20]
  1. ^ make-heap is the operation of building a heap from a sequence of n unsorted elements. It can be done in Θ(n) time whenever meld runs in O(log n) time (where both complexities can be amortized).[6][7] Another algorithm achieves Θ(n) for binary heaps.[8]
  2. ^ a b c For persistent heaps (not supporting decrease-key), a generic transformation reduces the cost of meld to that of insert, while the new cost of delete-min is the sum of the old costs of delete-min and meld.[11] Here, it makes meld run in Θ(1) time (amortized, if the cost of insert is) while delete-min still runs in O(log n). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.[10]
  3. ^ Lower bound of  [14] upper bound of  [15]
  4. ^ a b Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a persistent data structure achieving the same optimum, except that decrease-key is not supported.

Applications

edit

See also

edit
  • Weak heap, a combination of the binary heap and binomial heap data structures

References

edit
  1. ^ a b c d e f g h i j k l m n o p q Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 19: Binomial Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 455–475. ISBN 0-262-03293-7.
  2. ^ Vuillemin, Jean (1 April 1978). "A data structure for manipulating priority queues". Communications of the ACM. 21 (4): 309–315. doi:10.1145/359460.359478.
  3. ^ a b c d e f g h i j Brown, Mark R. (1978). "Implementation and analysis of binomial queue algorithms". SIAM Journal on Computing. 7 (3): 298–319. doi:10.1137/0207026. MR 0483830.
  4. ^ Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x
  5. ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
  6. ^ a b c Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. doi:10.1137/0215004. ISSN 0097-5397.
  7. ^ a b Tarjan, Robert (1983). "3.3. Leftist heaps". Data Structures and Network Algorithms. pp. 38–42. doi:10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
  8. ^ Hayward, Ryan; McDiarmid, Colin (1991). "Average Case Analysis of Heap Building by Repeated Insertion" (PDF). J. Algorithms. 12: 126–153. CiteSeerX 10.1.1.353.7888. doi:10.1016/0196-6774(91)90027-v. Archived from the original (PDF) on 5 February 2016. Retrieved 28 January 2016.
  9. ^ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 30 September 2019.
  10. ^ a b Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x
  11. ^ Okasaki, Chris (1998). "10.2. Structural Abstraction". Purely Functional Data Structures (1st ed.). pp. 158–162. ISBN 9780521631242.
  12. ^ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
  13. ^ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
  14. ^ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
  15. ^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
  16. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  17. ^ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
  18. ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
  19. ^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  20. ^ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
edit