data_structures.heap.skew_heap
==============================

.. py:module:: data_structures.heap.skew_heap


Attributes
----------

.. autoapisummary::

   data_structures.heap.skew_heap.T


Classes
-------

.. autoapisummary::

   data_structures.heap.skew_heap.SkewHeap
   data_structures.heap.skew_heap.SkewNode


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

.. py:class:: SkewHeap(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/Skew_heap
   Visualization: https://www.cs.usfca.edu/~galles/visualization/SkewHeap.html

   >>> list(SkewHeap([2, 3, 1, 5, 1, 7]))
   [1, 1, 2, 3, 5, 7]

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

   >>> sh.insert(1)
   >>> sh.insert(-1)
   >>> sh.insert(0)
   >>> list(sh)
   [-1, 0, 1]


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

      Check if the heap is not empty.

      >>> sh = SkewHeap()
      >>> bool(sh)
      False
      >>> sh.insert(1)
      >>> bool(sh)
      True
      >>> sh.clear()
      >>> bool(sh)
      False



   .. py:method:: __iter__() -> collections.abc.Iterator[T]

      Returns sorted list containing all the values in the heap.

      >>> sh = SkewHeap([3, 1, 3, 7])
      >>> list(sh)
      [1, 3, 3, 7]



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

      Clear the heap.

      >>> sh = SkewHeap([3, 1, 3, 7])
      >>> sh.clear()
      >>> sh.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.

      >>> sh = SkewHeap()
      >>> sh.insert(3)
      >>> sh.insert(1)
      >>> sh.insert(3)
      >>> sh.insert(7)
      >>> list(sh)
      [1, 3, 3, 7]



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

      Pop the smallest value from the heap and return it.

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



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

      Return the smallest value from the heap.

      >>> sh = SkewHeap()
      >>> sh.insert(3)
      >>> sh.top()
      3
      >>> sh.insert(1)
      >>> sh.top()
      1
      >>> sh.insert(3)
      >>> sh.top()
      1
      >>> sh.insert(7)
      >>> sh.top()
      1



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



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

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


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


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


      Merge 2 nodes together.
      >>> SkewNode.merge(SkewNode(10),SkewNode(-10.5)).value
      -10.5
      >>> SkewNode.merge(SkewNode(10),SkewNode(10.5)).value
      10
      >>> SkewNode.merge(SkewNode(10),SkewNode(10)).value
      10
      >>> SkewNode.merge(SkewNode(-100),SkewNode(-10.5)).value
      -100



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


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



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



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


      Return the value of the node.

      >>> SkewNode(0).value
      0
      >>> SkewNode(3.14159).value
      3.14159
      >>> SkewNode("hello").value
      'hello'
      >>> SkewNode(None).value

      >>> SkewNode(True).value
      True
      >>> SkewNode([]).value
      []
      >>> SkewNode({}).value
      {}
      >>> SkewNode(set()).value
      set()
      >>> SkewNode(0.0).value
      0.0
      >>> SkewNode(-1e-10).value
      -1e-10
      >>> SkewNode(10).value
      10
      >>> SkewNode(-10.5).value
      -10.5
      >>> SkewNode().value
      Traceback (most recent call last):
      ...
      TypeError: SkewNode.__init__() missing 1 required positional argument: 'value'



.. py:data:: T