data_structures.heap.randomized_heap
====================================

.. py:module:: data_structures.heap.randomized_heap


Attributes
----------

.. autoapisummary::

   data_structures.heap.randomized_heap.T


Classes
-------

.. autoapisummary::

   data_structures.heap.randomized_heap.RandomizedHeap
   data_structures.heap.randomized_heap.RandomizedHeapNode


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

.. py:class:: RandomizedHeap(data: collections.abc.Iterable[T] | None = ())

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ ]


   A data structure that allows inserting a new value and to pop the smallest
   values. Both operations take O(logN) time where N is the size of the
   structure.
   Wiki: https://en.wikipedia.org/wiki/Randomized_meldable_heap

   >>> RandomizedHeap([2, 3, 1, 5, 1, 7]).to_sorted_list()
   [1, 1, 2, 3, 5, 7]

   >>> rh = RandomizedHeap()
   >>> rh.pop()
   Traceback (most recent call last):
       ...
   IndexError: Can't get top element for the empty heap.

   >>> rh.insert(1)
   >>> rh.insert(-1)
   >>> rh.insert(0)
   >>> rh.to_sorted_list()
   [-1, 0, 1]


   .. py:method:: __bool__() -> bool

      Check if the heap is not empty.

      >>> rh = RandomizedHeap()
      >>> bool(rh)
      False
      >>> rh.insert(1)
      >>> bool(rh)
      True
      >>> rh.clear()
      >>> bool(rh)
      False



   .. py:method:: clear() -> None

      Clear the heap.

      >>> rh = RandomizedHeap([3, 1, 3, 7])
      >>> rh.clear()
      >>> rh.pop()
      Traceback (most recent call last):
          ...
      IndexError: Can't get top element for the empty heap.



   .. py:method:: insert(value: T) -> None

      Insert the value into the heap.

      >>> rh = RandomizedHeap()
      >>> rh.insert(3)
      >>> rh.insert(1)
      >>> rh.insert(3)
      >>> rh.insert(7)
      >>> rh.to_sorted_list()
      [1, 3, 3, 7]



   .. py:method:: pop() -> T | None

      Pop the smallest value from the heap and return it.

      >>> rh = RandomizedHeap([3, 1, 3, 7])
      >>> rh.pop()
      1
      >>> rh.pop()
      3
      >>> rh.pop()
      3
      >>> rh.pop()
      7
      >>> rh.pop()
      Traceback (most recent call last):
          ...
      IndexError: Can't get top element for the empty heap.



   .. py:method:: to_sorted_list() -> list[Any]

      Returns sorted list containing all the values in the heap.

      >>> rh = RandomizedHeap([3, 1, 3, 7])
      >>> rh.to_sorted_list()
      [1, 3, 3, 7]



   .. py:method:: top() -> T

      Return the smallest value from the heap.

      >>> rh = RandomizedHeap()
      >>> rh.insert(3)
      >>> rh.top()
      3
      >>> rh.insert(1)
      >>> rh.top()
      1
      >>> rh.insert(3)
      >>> rh.top()
      1
      >>> rh.insert(7)
      >>> rh.top()
      1



   .. py:attribute:: _root
      :type:  RandomizedHeapNode[T] | None
      :value: None



.. py:class:: RandomizedHeapNode(value: T)

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ ]


   One node of the randomized heap. Contains the value and references to
   two children.


   .. py:method:: merge(root1: RandomizedHeapNode[T] | None, root2: RandomizedHeapNode[T] | None) -> RandomizedHeapNode[T] | None
      :staticmethod:


      Merge 2 nodes together.

      >>> rhn1 = RandomizedHeapNode(10)
      >>> rhn2 = RandomizedHeapNode(20)
      >>> RandomizedHeapNode.merge(rhn1, rhn2).value
      10

      >>> rhn1 = RandomizedHeapNode(20)
      >>> rhn2 = RandomizedHeapNode(10)
      >>> RandomizedHeapNode.merge(rhn1, rhn2).value
      10

      >>> rhn1 = RandomizedHeapNode(5)
      >>> rhn2 = RandomizedHeapNode(0)
      >>> RandomizedHeapNode.merge(rhn1, rhn2).value
      0



   .. py:attribute:: _value
      :type:  T


   .. py:attribute:: left
      :type:  RandomizedHeapNode[T] | None
      :value: None



   .. py:attribute:: right
      :type:  RandomizedHeapNode[T] | None
      :value: None



   .. py:property:: value
      :type: T


      Return the value of the node.

      >>> rhn = RandomizedHeapNode(10)
      >>> rhn.value
      10
      >>> rhn = RandomizedHeapNode(-10)
      >>> rhn.value
      -10



.. py:data:: T