



'''simple docstring'''





from __future__ import annotations

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






class  lowerCamelCase_   (    SCREAMING_SNAKE_CASE_					):
  """simple docstring"""




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




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




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




_UpperCamelCase							    =						TypeVar('T', bound=Comparable)






class  lowerCamelCase_   (    Generic[T]					):
  """simple docstring"""




  def __init__(			self				:     Optional[Any]       ) -> None:
    __lowerCamelCase	:	list[T]   	=			[]
    __lowerCamelCase	:	int   	=			0




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




  def 						_lowercase					(			self				:     List[str]      ,     _a				:     int       ) -> int | None:
    if child_idx > 0:
      return (child_idx - 1) // 2
    return None




  def 						_lowercase					(			self				:     int      ,     _a				:     int       ) -> int | None:
    __lowerCamelCase	:	Any   	=			2 * parent_idx + 1
    if left_child_index < self.heap_size:
      return left_child_index
    return None




  def 						_lowercase					(			self				:     Optional[Any]      ,     _a				:     int       ) -> int | None:
    __lowerCamelCase	:	Optional[Any]   	=			2 * parent_idx + 2
    if right_child_index < self.heap_size:
      return right_child_index
    return None




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




  def 						_lowercase					(			self				:     List[str]      ,     _a				:     Iterable[T]       ) -> None:
    __lowerCamelCase	:	Any   	=			list(_a       )
    __lowerCamelCase	:	Optional[int]   	=			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(_a       )




  def 						_lowercase					(			self				:     List[Any]       ) -> T:
    if self.heap_size >= 2:
      __lowerCamelCase	:	Any   	=			self.h[0]
      __lowerCamelCase	:	int   	=			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 						_lowercase					(			self				:     Tuple      ,     _a				:     T       ) -> None:
    self.h.append(_a       )
    __lowerCamelCase	:	Optional[int]   	=			(self.heap_size - 1) // 2
    self.heap_size += 1
    while idx >= 0:
      self.max_heapify(_a       )
      __lowerCamelCase	:	Tuple   	=			(idx - 1) // 2




  def 						_lowercase					(			self				:     List[str]       ) -> None:
    __lowerCamelCase	:	Union[str, Any]   	=			self.heap_size
    for j in range(size - 1      ,     0      ,     -1       ):
      __lowerCamelCase	,__lowerCamelCase	:	Any   	=			self.h[j], self.h[0]
      self.heap_size -= 1
      self.max_heapify(0       )
    __lowerCamelCase	:	List[str]   	=			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, 10, 8],
       [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5],
       [-45, -2, -5],
   ]:
      print(f'''unsorted array: {unsorted}''')

      _UpperCamelCase							    =						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(100)
      print(f'''after new value 100 inserted: {heap}''')

      heap.heap_sort()
      print(f'''heap-sorted array: {heap}\n''')











'''simple docstring'''





import math
from timeit import timeit

def 	a_					(							_lowerCAmelCase	)				->				int:
  __lowerCamelCase	:	int   	=			0
  __lowerCamelCase	:	Optional[int]   	=			abs(_lowerCAmelCase	)
  while True:
    __lowerCamelCase	:	List[str]   	=			n // 10
    digits += 1
    if n == 0:
      break
  return digits

def 	a_					(							_lowerCAmelCase	)				->				int:
  return 1 if n == 0 else math.floor(math.log(abs(_lowerCAmelCase	)	,10	) + 1	)

def 	a_					(							_lowerCAmelCase	)				->				int:
  return len(str(abs(_lowerCAmelCase	)	)	)

def 	a_					(							)				->				None:
  from collections.abc import Callable

  def benchmark_a_function(_lowerCAmelCase	,_lowerCAmelCase	) -> None:
    __lowerCamelCase	:	Any   	=			F'{func.__name__}({value})'
    __lowerCamelCase	:	int   	=			timeit(F'__main__.{call}'	,setup='import __main__'	)
    print(F'{call}: {func(_lowerCAmelCase	)} -- {timing} seconds'	)

  for value in (262144, 1125899906842624, 1267650600228229401496703205376):
    for func in (num_digits, num_digits_fast, num_digits_faster):
      benchmark_a_function(_lowerCAmelCase	,_lowerCAmelCase	)
    print()


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   benchmark()






