***************
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.

.. admonition:: Activity
    :class: activity

    * How do you proceed?

*  It seems difficult to design a data structure that efficiently supports merging.
*  Meaning that the operation is in :math:`O(N)`.
*  Merging require copying one array into another.

*  So, :math:`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 :math:`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.
*  :math:`B_k` is a binomial tree of height :math:`k`.
*  :math:`B_k` is formed by attaching  :math:`B_{k-1}` to the root of another :math:`B_{k-1}`.

.. admonition:: Example
    :class: example

    *  A binomial tree of height 0 is a one-node tree.
    *  Etc...

    The following figure illustrates different binomial trees.

    .. figure:: ./img/binomial_trees.*
        :align: center


.. important::

    *  Binomial trees of height :math:`k` have exactly :math:`2^k` nodes.
    *  The number of nodes at depth :math:`d` is the binomial coefficient :math:`\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.

.. figure:: ./img/merge_01.png
    :align: center


*  We define :math:`H_3` the new binomial queue.
*  We need to take care of the :math:`B_0`.

*  :math:`H_1` does not have a binomial tree of height 0.
*  :math:`H_2` does, so we can just add it to :math:`H_3`.

.. figure:: ./img/merge_02.png
    :align: center

*  Now we consider the binomial tree of height 1.

*  :math:`H_1` and :math:`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.

.. figure:: ./img/merge_03.png
    :align: center

*  There are now three binomial trees of height 2.
*  We keep one binomial tree of height 2 and merge the other two.

.. figure:: ./img/merge_04.png
    :align: center

*  Since :math:`H_1` and :math:`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 :math:`O(\log N)`.


.. admonition:: Example
    :class: example

    *  In this example we will insert the integers from 1 to 7 to an empty binomial queue.
    *  We start by inserting 1.

    .. figure:: ./img/insert_01_binomial.png
        :align: center

    |

    *  We now insert 2.

    .. figure:: ./img/insert_02_binomial.png
            :align: center

    |

    *  We now insert 3.

    .. figure:: ./img/insert_03.png
            :align: center

    |

    *  We now insert 4.

    .. figure:: ./img/insert_04.png
            :align: center

    |

    *  We now insert 5.

    .. figure:: ./img/insert_05.png
            :align: center

    |

    *  We now insert 6.

    .. figure:: ./img/insert_06.png
            :align: center
    
    |
    
    *  We now insert 7.

    .. figure:: ./img/insert_07.png
            :align: center
    |

DeleteMin
---------

*  Consider a binomial queue denoted :math:`H`.
*  Delete the minimum element by finding the smallest root.

*  Let this tree be :math:`B_k`.
*  Remove it from :math:`H`, creating a new queue :math:`H'`.
*  Remove the root of :math:`B_k`.
*  It creates binomial trees :math:`B_0, B_1, \dots, B_{k-1}` in a queue :math:`H''`.
*  Merge :math:`H'` and :math:`H''`.


.. admonition:: Example
    :class: example

    *  Consider the following binomial queue :math:`H`.
    *  We want to remove the smallest element(:math:`12`).

    .. figure:: ./img/delete_01_binomial.png
        :align: center

        :math:`H`

    |

    *  We remove :math:`B_3` from :math:`H` creating :math:`H'`.

    .. figure:: ./img/delete_02_binomial.png
        :align: center

    |

    *  We obtain :math:`H''` the binomial queue creating after deleting 12 from :math:`B_3`.

    .. figure:: ./img/delete_03_binomial.png
        :align: center

    |

    *  We are merging :math:`H'` and :math:`H''`.

    .. figure:: ./img/delete_04_binomial.png
        :align: center