'''simple docstring'''

from __future__ import annotations

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




class    lowerCamelCase__  (   __snake_case     ):



   @abstractmethod
   def __lt__(    self					,      lowerCAmelCase__     )				->     bool:
        """simple docstring"""





        pass



   @abstractmethod
   def __gt__(    self					,      lowerCAmelCase__     )				->     bool:
        """simple docstring"""





        pass




   @abstractmethod
   def __eq__(    self					,      lowerCAmelCase__     )				->     bool:
        """simple docstring"""





        pass




_lowerCamelCase :				Tuple														= TypeVar("""T""", bound=Comparable)




class    lowerCamelCase__  (   Generic[T]     ):



   def __init__(    self     )				->     None:
        """simple docstring"""





        _UpperCamelCase  :list[T]       =[]
        _UpperCamelCase  :int       =0



   def __repr__(    self     )				->     str:
        """simple docstring"""





        return str(self.h     )



   def  _UpperCamelCase		(    self					,      lowerCAmelCase__     )				->     int | None:
        """simple docstring"""





        if child_idx > 0:
             return (child_idx - 1) // 2
        return None



   def  _UpperCamelCase		(    self					,      lowerCAmelCase__     )				->     int | None:
        """simple docstring"""





        _UpperCamelCase  :Any       =2 * parent_idx + 1
        if left_child_index < self.heap_size:
             return left_child_index
        return None



   def  _UpperCamelCase		(    self					,      lowerCAmelCase__     )				->     int | None:
        """simple docstring"""





        _UpperCamelCase  :Union[str, Any]       =2 * parent_idx + 2
        if right_child_index < self.heap_size:
             return right_child_index
        return None



   def  _UpperCamelCase		(    self					,      lowerCAmelCase__     )				->     None:
        """simple docstring"""





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



   def  _UpperCamelCase		(    self					,      lowerCAmelCase__     )				->     None:
        """simple docstring"""





        _UpperCamelCase  :Union[str, Any]       =list(lowerCAmelCase__     )
        _UpperCamelCase  :Union[str, Any]       =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(lowerCAmelCase__     )



   def  _UpperCamelCase		(    self     )				->     T:
        """simple docstring"""





        if self.heap_size >= 2:
             _UpperCamelCase  :List[Any]       =self.h[0]
             _UpperCamelCase  :Tuple       =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					,      lowerCAmelCase__     )				->     None:
        """simple docstring"""





        self.h.append(lowerCAmelCase__     )
        _UpperCamelCase  :Optional[int]       =(self.heap_size - 1) // 2
        self.heap_size += 1
        while idx >= 0:
             self.max_heapify(lowerCAmelCase__     )
             _UpperCamelCase  :List[str]       =(idx - 1) // 2




   def  _UpperCamelCase		(    self     )				->     None:
        """simple docstring"""





        _UpperCamelCase  :Optional[Any]       =self.heap_size
        for j in range(size - 1					,      0					,      -1     ):
             _UpperCamelCase       ,      _UpperCamelCase  :Union[str, Any]       =self.h[j], self.h[0]
             self.heap_size -= 1
             self.max_heapify(0     )
        _UpperCamelCase  :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],
          [1_03, 9, 1, 7, 11, 15, 25, 2_01, 2_09, 1_07, 5],
          [-45, -2, -5],
      ]:
            print(f"unsorted array: {unsorted}")

            _lowerCamelCase :				Heap[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_00)
            print(f"after new value 100 inserted: {heap}")

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

"""simple docstring"""




def __snake_case (      UpperCamelCase    )       ->    float:


		"""simple docstring"""





		return -num if num < 0 else num

def __snake_case (      UpperCamelCase    )       ->    int:


		"""simple docstring"""





		if len(UpperCamelCase    ) == 0:
				raise ValueError('''abs_min() arg is an empty sequence'''    )
		a__   		=     x[0]
		for i in x:
				if abs_val(UpperCamelCase    ) < abs_val(UpperCamelCase    ):
						a__   		=     i
		return j

def __snake_case (      UpperCamelCase    )       ->    int:


		"""simple docstring"""





		if len(UpperCamelCase    ) == 0:
				raise ValueError('''abs_max() arg is an empty sequence'''    )
		a__   		=     x[0]
		for i in x:
				if abs(UpperCamelCase    ) > abs(UpperCamelCase    ):
						a__   		=     i
		return j

def __snake_case (      UpperCamelCase    )       ->    int:


		"""simple docstring"""





		if len(UpperCamelCase    ) == 0:
				raise ValueError('''abs_max_sort() arg is an empty sequence'''    )
		return sorted(UpperCamelCase						,					key=UpperCamelCase    )[-1]

def __snake_case (      )       ->    Optional[int]:


		"""simple docstring"""





		assert abs_val(0    ) == 0
		assert abs_val(34    ) == 34
		assert abs_val(-100_000_000_000    ) == 100_000_000_000

		a__   		=     [-3, -1, 2, -11]
		assert abs_max(UpperCamelCase    ) == -11
		assert abs_max_sort(UpperCamelCase    ) == -11
		assert abs_min(UpperCamelCase    ) == -1


if __name__ == "__main__":
					import doctest

					doctest.testmod()

					test_abs_val()
					print(abs_val(-34))  # --> 34




