Binomial Queues

• Binomial queue


  A collection of heap-ordered trees, known as a forest
• Binomial tree


  • At most one binomial tree of every height
  • A binomial tree of height 0 is a one-node tree
  • A binomial tree, B , of height k is formed by attaching a binomial tree, B , to the root of another binomial tree, B
• Binomial trees of height k have exactly 2 nodes, and the number of nodes at depth d is the binomial coefficient
• Imposing heap order on the binomial trees and allowing at most one binomial tree of any height, a priority queue of any size can be represented by a collection of binomial trees
• The minimum element can be found by scanning the roots of all the trees, which takes O(log N) time
• Merging two binomial queues

  1. Add the two queues together

  2. If one queue has a binomial tree of height k and the other doesn't, use the tree from the first queue

  3. If both queues have a binomial tree of height k, merge them by making the larger root a subtree of the smaller, creating a binomial tree of height k+1

  4. Keep one binomial tree of each height in the merged queue
• Merging two binomial trees takes constant time, and there are O(log N) binomial trees, so the merge takes O(log N) time in the worst case
• Insertion


  1. Create a one-node tree and perform a merge

  2. The running time is proportional to i + 1, where i is the height of the smallest nonexistent binomial tree in the priority queue
• Insertions take constant time on average in a binomial queue
• DeleteMin


  1. Find the binomial tree with the smallest root

  2. Remove that tree from the forest, forming H'

  3. Remove the root of that tree, creating binomial trees B , B , …, B , which collectively form H''

  4. Merge H' and H''
• DeleteMin takes O(log N) time
• Binomial queue implementation

  • Children of each node are kept in a linked list, with a reference to the first child
  • Subtrees are ordered by decreasing size, to enable efficient merging
• Binomial queue


  • Requires the ability to find all the subtrees of the root quickly
  • The children of each node are kept in a linked list, and each node has a reference to its first child (if any)
  • The children in a binomial tree are arranged in decreasing rank
• The deleteMin operation requires the ability to find all the subtrees of the root quickly
• The standard representation of general trees is required for the deleteMin operation
• The binomial queue will be an array of binomial trees
• Node in a binomial tree

  Contains the data, first child, and right sibling
• Merging two binomial queues

  1. Combine equal-sized binomial trees

  2. Depending on the cases, form the tree of rank i and the carry tree of rank i+1
• Binomial queues can be extended to support operations like decreaseKey and delete when the position of the affected element is known