data_structures.heap.binomial_heap
==================================

.. py:module:: data_structures.heap.binomial_heap

.. autoapi-nested-parse::

   Binomial Heap
   Reference: Advanced Data Structures, Peter Brass



Classes
-------

.. autoapisummary::

   data_structures.heap.binomial_heap.BinomialHeap
   data_structures.heap.binomial_heap.Node


Module Contents
---------------

.. py:class:: BinomialHeap(bottom_root=None, min_node=None, heap_size=0)

   Min-oriented priority queue implemented with the Binomial Heap data
   structure implemented with the BinomialHeap class. It supports:
       - Insert element in a heap with n elements: Guaranteed logn, amoratized 1
       - Merge (meld) heaps of size m and n: O(logn + logm)
       - Delete Min: O(logn)
       - Peek (return min without deleting it): O(1)

   Example:

   Create a random permutation of 30 integers to be inserted and 19 of them deleted
   >>> import numpy as np
   >>> permutation = np.random.permutation(list(range(30)))

   Create a Heap and insert the 30 integers
   __init__() test
   >>> first_heap = BinomialHeap()

   30 inserts - insert() test
   >>> for number in permutation:
   ...     first_heap.insert(number)

   Size test
   >>> first_heap.size
   30

   Deleting - delete() test
   >>> [int(first_heap.delete_min()) for _ in range(20)]
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

   Create a new Heap
   >>> second_heap = BinomialHeap()
   >>> vals = [17, 20, 31, 34]
   >>> for value in vals:
   ...     second_heap.insert(value)


   The heap should have the following structure:

                   17
                  /  \
                 #    31
                     /  \
                   20    34
                  /  \  /  \
                 #    # #   #

   preOrder() test
   >>> " ".join(str(x) for x in second_heap.pre_order())
   "(17, 0) ('#', 1) (31, 1) (20, 2) ('#', 3) ('#', 3) (34, 2) ('#', 3) ('#', 3)"

   printing Heap - __str__() test
   >>> print(second_heap)
   17
   -#
   -31
   --20
   ---#
   ---#
   --34
   ---#
   ---#

   mergeHeaps() test
   >>>
   >>> merged = second_heap.merge_heaps(first_heap)
   >>> merged.peek()
   17

   values in merged heap; (merge is inplace)
   >>> results = []
   >>> while not first_heap.is_empty():
   ...     results.append(int(first_heap.delete_min()))
   >>> results
   [17, 20, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 34]


   .. py:method:: __str__()

      Overwriting str for a pre-order print of nodes in heap;
      Performance is poor, so use only for small examples



   .. py:method:: __traversal(curr_node, preorder, level=0)

      Pre-order traversal of nodes



   .. py:method:: delete_min()

      delete min element and return it



   .. py:method:: insert(val)

      insert a value in the heap



   .. py:method:: is_empty()


   .. py:method:: merge_heaps(other)

      In-place merge of two binomial heaps.
      Both of them become the resulting merged heap



   .. py:method:: peek()

      return min element without deleting it



   .. py:method:: pre_order()

      Returns the Pre-order representation of the heap including
      values of nodes plus their level distance from the root;
      Empty nodes appear as #



   .. py:attribute:: bottom_root
      :value: None



   .. py:attribute:: min_node
      :value: None



   .. py:attribute:: size
      :value: 0



.. py:class:: Node(val)

   Node in a doubly-linked binomial tree, containing:
       - value
       - size of left subtree
       - link to left, right and parent nodes


   .. py:method:: merge_trees(other)

      In-place merge of two binomial trees of equal size.
      Returns the root of the resulting tree



   .. py:attribute:: left
      :value: None



   .. py:attribute:: left_tree_size
      :value: 0



   .. py:attribute:: parent
      :value: None



   .. py:attribute:: right
      :value: None



   .. py:attribute:: val