






'''simple docstring'''







from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar






class 					a__    (			_a						):
     '''simple docstring'''







     @abstractmethod
     def __lt__(self    :	T				,				lowercase__    :	T					)  ->       bool:
           pass






     @abstractmethod
     def __gt__(self    :	T				,				lowercase__    :	T					)  ->       bool:
           pass






     @abstractmethod
     def __eq__(self    :	T				,				lowercase__    :	object					)  ->       bool:
           pass







__A      :       int      = TypeVar('T', bound=Comparable)






class 					a__    (			Generic[T]						):
     '''simple docstring'''







     def __init__(self    :	List[str]					)  ->       None:
           __A		   =      []
           __A		   =      0






     def __repr__(self    :	Tuple					)  ->       str:
           return str(self.h					)






     def     _UpperCamelCase   (self    :	Any				,				lowercase__    :	int					)  ->       int | None:
           if child_idx > 0:
                 return (child_idx - 1) // 2
           return None






     def     _UpperCamelCase   (self    :	List[str]				,				lowercase__    :	int					)  ->       int | None:
           __A		   =      2 * parent_idx + 1
           if left_child_index < self.heap_size:
                 return left_child_index
           return None






     def     _UpperCamelCase   (self    :	Tuple				,				lowercase__    :	int					)  ->       int | None:
           __A		   =      2 * parent_idx + 2
           if right_child_index < self.heap_size:
                 return right_child_index
           return None






     def     _UpperCamelCase   (self    :	str				,				lowercase__    :	int					)  ->       None:
           if index < self.heap_size:
                 __A		   =      index
                 __A		   =      self.left_child_idx(lowercase__					)
                 __A		   =      self.right_child_idx(lowercase__					)
                 # check which child is larger than its parent
                 if left_child is not None and self.h[left_child] > self.h[violation]:
                       __A		   =      left_child
                 if right_child is not None and self.h[right_child] > self.h[violation]:
                       __A		   =      right_child
                 # if violation indeed exists
                 if violation != index:
                       # swap to fix the violation
                       __A   ,				__A		   =      self.h[index], self.h[violation]
                       # fix the subsequent violation recursively if any
                       self.max_heapify(lowercase__					)






     def     _UpperCamelCase   (self    :	int				,				lowercase__    :	Iterable[T]					)  ->       None:
           __A		   =      list(lowercase__					)
           __A		   =      len(self.h					)
           if self.heap_size > 1:
                 # max_heapify from right to left but exclude leaves (last level)
                 for i in range(self.heap_size // 2 - 1				,				-1				,				-1					):
                       self.max_heapify(lowercase__					)






     def     _UpperCamelCase   (self    :	Any					)  ->       T:
           if self.heap_size >= 2:
                 __A		   =      self.h[0]
                 __A		   =      self.h.pop(-1					)
                 self.heap_size -= 1
                 self.max_heapify(0					)
                 return me
           elif self.heap_size == 1:
                 self.heap_size -= 1
                 return self.h.pop(-1					)
           else:
                 raise Exception("Empty heap"					)






     def     _UpperCamelCase   (self    :	Dict				,				lowercase__    :	T					)  ->       None:
           self.h.append(lowercase__					)
           __A		   =      (self.heap_size - 1) // 2
           self.heap_size += 1
           while idx >= 0:
                 self.max_heapify(lowercase__					)
                 __A		   =      (idx - 1) // 2






     def     _UpperCamelCase   (self    :	int					)  ->       None:
           __A		   =      self.heap_size
           for j in range(size - 1				,				0				,				-1					):
                 __A   ,				__A		   =      self.h[j], self.h[0]
                 self.heap_size -= 1
                 self.max_heapify(0					)
           __A		   =      size


if __name__ == "__main__":
       import doctest

       # run doc test
       doctest.testmod()

       # demo
       for unsorted in [
           [0],
           [2],
           [3, 5],
           [5, 3],
           [5, 5],
           [0, 0, 0, 0],
           [1, 1, 1, 1],
           [2, 2, 3, 5],
           [0, 2, 2, 3, 5],
           [2, 5, 3, 0, 2, 3, 0, 3],
           [6, 1, 2, 7, 9, 3, 4, 5, 1_0, 8],
           [1_0_3, 9, 1, 7, 1_1, 1_5, 2_5, 2_0_1, 2_0_9, 1_0_7, 5],
           [-4_5, -2, -5],
       ]:
              print(F"""unsorted array: {unsorted}""")

              __A      :       Optional[int]      = Heap()
              heap.build_max_heap(unsorted)
              print(F"""after build heap: {heap}""")

              print(F"""max value: {heap.extract_max()}""")
              print(F"""after max value removed: {heap}""")

              heap.insert(1_0_0)
              print(F"""after new value 100 inserted: {heap}""")

              heap.heap_sort()
              print(F"""heap-sorted array: {heap}\n""")










'''simple docstring'''







from __future__ import annotations

from queue import Queue






class 					a__    :
     '''simple docstring'''







     def __init__(self    :	Any					)  ->       None:
           __A		   =      {}






     def     _UpperCamelCase   (self    :	Optional[int]					)  ->       None:
           for i in self.vertices:
                 print(lowercase__				,				" : "				,				" -> ".join([str(lowercase__					) for j in self.vertices[i]]					)					)






     def     _UpperCamelCase   (self    :	Union[str, Any]				,				lowercase__    :	int				,				lowercase__    :	int					)  ->       None:
           if from_vertex in self.vertices:
                 self.vertices[from_vertex].append(lowercase__					)
           else:
                 __A		   =      [to_vertex]






     def     _UpperCamelCase   (self    :	Optional[int]				,				lowercase__    :	int					)  ->       set[int]:
           __A		   =      set()

           # create a first in first out queue to store all the vertices for BFS
           __A		   =      Queue()

           # mark the source node as visited and enqueue it
           visited.add(lowercase__					)
           queue.put(lowercase__					)

           while not queue.empty():
                 __A		   =      queue.get()

                 # loop through all adjacent vertex and enqueue it if not yet visited
                 for adjacent_vertex in self.vertices[vertex]:
                       if adjacent_vertex not in visited:
                             queue.put(lowercase__					)
                             visited.add(lowercase__					)
           return visited


if __name__ == "__main__":
       from doctest import testmod

       testmod(verbose=True)

       __A      :       Dict      =	Graph()
       g.add_edge(0, 1)
       g.add_edge(0, 2)
       g.add_edge(1, 2)
       g.add_edge(2, 0)
       g.add_edge(2, 3)
       g.add_edge(3, 3)

       g.print_graph()
       # 0  :  1 -> 2
       # 1  :  2
       # 2  :  0 -> 3
       # 3  :  3

       assert sorted(g.bfs(2)) == [0, 1, 2, 3]


