Topic 11 - Binomial Queues
Introduction
Consider a problem in which you use a priority queue.
Now, you receive another priority queue.
You need to merge both of them.
Activity
How do you proceed?
It seems difficult to design a data structure that efficiently supports merging.
Meaning that the operation is in \(O(N)\).
Merging require copying one array into another.
So, \(O(N)\).
How can we solve this for priority queues.
What is a Binomial Queue?
The Binomial Queues ADT needs to have the following operations:
Insertion
Deletion
Merging
Every operation are \(O(\log N)\) in the worst-case.
However, insertion takes constant time in average.
Structure
The most interesting thing about a binomial queue is its structure.
It’s not a heap-ordered tree, like binary heaps, but a collection of heap-ordered trees.
Note
A collection of trees is called a forest.
The idea:
Each heap-ordered tree in the binomial queues is a binomial tree.
There is at most one binomial tree of every height.
\(B_k\) is a binomial tree of height \(k\).
\(B_k\) is formed by attaching \(B_{k-1}\) to the root of another \(B_{k-1}\).
Example
A binomial tree of height 0 is a one-node tree.
Etc…
The following figure illustrates different binomial trees.
Important
Binomial trees of height \(k\) have exactly \(2^k\) nodes.
The number of nodes at depth \(d\) is the binomial coefficient \(\binom{k}{d}\).
Binomial Queue Operations
We need to discuss the three main operations of the binomial queues.
Merging
Merging is an easy operation.
We will use an example.
We consider the following binomial queues.
We define \(H_3\) the new binomial queue.
We need to take care of the \(B_0\).
\(H_1\) does not have a binomial tree of height 0.
\(H_2\) does, so we can just add it to \(H_3\).
Now we consider the binomial tree of height 1.
\(H_1\) and \(H_2\) have binomial trees of height 1.
We merge them by making the larger root a subtree of the smaller tree.
We obtain a binomial tree of height 2.
There are now three binomial trees of height 2.
We keep one binomial tree of height 2 and merge the other two.
Since \(H_1\) and \(H_2\) have no trees of height 3 we stop there.
Insert
Insertion is a special case of merging.
We create a one-node tree (tree of height 0) and perform a merge.
The worst-case time of this operation is \(O(\log N)\).
Example
In this example we will insert the integers from 1 to 7 to an empty binomial queue.
We start by inserting 1.
We now insert 2.
We now insert 3.
We now insert 4.
We now insert 5.
We now insert 6.
We now insert 7.
DeleteMin
Consider a binomial queue denoted \(H\).
Delete the minimum element by finding the smallest root.
Let this tree be \(B_k\).
Remove it from \(H\), creating a new queue \(H'\).
Remove the root of \(B_k\).
It creates binomial trees \(B_0, B_1, \dots, B_{k-1}\) in a queue \(H''\).
Merge \(H'\) and \(H''\).
Example
Consider the following binomial queue \(H\).
We want to remove the smallest element(\(12\)).
We remove \(B_3\) from \(H\) creating \(H'\).
We obtain \(H''\) the binomial queue creating after deleting 12 from \(B_3\).
We are merging \(H'\) and \(H''\).