data_structures.heap.heap_generic
=================================

.. py:module:: data_structures.heap.heap_generic


Classes
-------

.. autoapisummary::

   data_structures.heap.heap_generic.Heap


Functions
---------

.. autoapisummary::

   data_structures.heap.heap_generic.test_heap


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

.. py:class:: Heap(key: collections.abc.Callable | None = None)

   A generic Heap class, can be used as min or max by passing the key function
   accordingly.


   .. py:method:: _cmp(i: int, j: int) -> bool

      Compares the two items using default comparison



   .. py:method:: _get_valid_parent(i: int) -> int

      Returns index of valid parent as per desired ordering among given index and
      both it's children



   .. py:method:: _heapify_down(index: int) -> None

      Fixes the heap in downward direction of given index



   .. py:method:: _heapify_up(index: int) -> None

      Fixes the heap in upward direction of given index



   .. py:method:: _left(i: int) -> int | None

      Returns left-child-index of given index if exists else None



   .. py:method:: _parent(i: int) -> int | None

      Returns parent index of given index if exists else None



   .. py:method:: _right(i: int) -> int | None

      Returns right-child-index of given index if exists else None



   .. py:method:: _swap(i: int, j: int) -> None

      Performs changes required for swapping two elements in the heap



   .. py:method:: delete_item(item: int) -> None

      Deletes given item from heap if present



   .. py:method:: extract_top() -> tuple | None

      Return top item tuple (Calculated value, item) from heap and removes it as well
      if present



   .. py:method:: get_top() -> tuple | None

      Returns top item tuple (Calculated value, item) from heap if present



   .. py:method:: insert_item(item: int, item_value: int) -> None

      Inserts given item with given value in heap



   .. py:method:: update_item(item: int, item_value: int) -> None

      Updates given item value in heap if present



   .. py:attribute:: arr
      :type:  list
      :value: []



   .. py:attribute:: key


   .. py:attribute:: pos_map
      :type:  dict


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



.. py:function:: test_heap() -> None

   >>> h = Heap()  # Max-heap
   >>> h.insert_item(5, 34)
   >>> h.insert_item(6, 31)
   >>> h.insert_item(7, 37)
   >>> h.get_top()
   [7, 37]
   >>> h.extract_top()
   [7, 37]
   >>> h.extract_top()
   [5, 34]
   >>> h.extract_top()
   [6, 31]
   >>> h = Heap(key=lambda x: -x)  # Min heap
   >>> h.insert_item(5, 34)
   >>> h.insert_item(6, 31)
   >>> h.insert_item(7, 37)
   >>> h.get_top()
   [6, -31]
   >>> h.extract_top()
   [6, -31]
   >>> h.extract_top()
   [5, -34]
   >>> h.extract_top()
   [7, -37]
   >>> h.insert_item(8, 45)
   >>> h.insert_item(9, 40)
   >>> h.insert_item(10, 50)
   >>> h.get_top()
   [9, -40]
   >>> h.update_item(10, 30)
   >>> h.get_top()
   [10, -30]
   >>> h.delete_item(10)
   >>> h.get_top()
   [9, -40]