
"""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     ,						_lowerCamelCase					) ->       bool:




										'''simple docstring'''
										pass
							@abstractmethod
							def __gt__(    self     ,						_lowerCamelCase					) ->       bool:




										'''simple docstring'''
										pass





							@abstractmethod
							def __eq__(    self     ,						_lowerCamelCase					) ->       bool:




										'''simple docstring'''
										pass





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

class 				__a    (   Generic[T]					):



							'''simple docstring'''







							def __init__(    self					) ->       None:




										'''simple docstring'''
										__lowercase						      =					[]
										__lowercase						      =					0
							def __repr__(    self					) ->       str:




										'''simple docstring'''
										return str(self.h					)
							def      SCREAMING_SNAKE_CASE	(    self     ,						_lowerCamelCase					) ->       int | None:




										'''simple docstring'''
										if child_idx > 0:
													return (child_idx - 1) // 2
										return None
							def      SCREAMING_SNAKE_CASE	(    self     ,						_lowerCamelCase					) ->       int | None:




										'''simple docstring'''
										__lowercase						      =					2 * parent_idx + 1
										if left_child_index < self.heap_size:
													return left_child_index
										return None
							def      SCREAMING_SNAKE_CASE	(    self     ,						_lowerCamelCase					) ->       int | None:




										'''simple docstring'''
										__lowercase						      =					2 * parent_idx + 2
										if right_child_index < self.heap_size:
													return right_child_index
										return None
							def      SCREAMING_SNAKE_CASE	(    self     ,						_lowerCamelCase					) ->       None:




										'''simple docstring'''
										if index < self.heap_size:
													__lowercase						      =					index
													__lowercase						      =					self.left_child_idx(_lowerCamelCase					)
													__lowercase						      =					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]:
																__lowercase						      =					left_child
													if right_child is not None and self.h[right_child] > self.h[violation]:
																__lowercase						      =					right_child
													# if violation indeed exists
													if violation != index:
																# swap to fix the violation
																__lowercase      ,				__lowercase						      =					self.h[index], self.h[violation]
																# fix the subsequent violation recursively if any
																self.max_heapify(_lowerCamelCase					)
							def      SCREAMING_SNAKE_CASE	(    self     ,						_lowerCamelCase					) ->       None:




										'''simple docstring'''
										__lowercase						      =					list(_lowerCamelCase					)
										__lowercase						      =					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      SCREAMING_SNAKE_CASE	(    self					) ->       T:




										'''simple docstring'''
										if self.heap_size >= 2:
													__lowercase						      =					self.h[0]
													__lowercase						      =					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      SCREAMING_SNAKE_CASE	(    self     ,						_lowerCamelCase					) ->       None:




										'''simple docstring'''
										self.h.append(_lowerCamelCase					)
										__lowercase						      =					(self.heap_size - 1) // 2
										self.heap_size += 1
										while idx >= 0:
													self.max_heapify(_lowerCamelCase					)
													__lowercase						      =					(idx - 1) // 2





							def      SCREAMING_SNAKE_CASE	(    self					) ->       None:




										'''simple docstring'''
										__lowercase						      =					self.heap_size
										for j in range(size - 1     ,						0     ,						-1					):
													__lowercase      ,				__lowercase						      =					self.h[j], self.h[0]
													self.heap_size -= 1
													self.max_heapify(0					)
										__lowercase						      =					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}")

										_lowercase							 =							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"""






from scipy.constants import g



def     lowerCAmelCase__ (		__magic_name__ ,      __magic_name__			)	->float:
			if mass < 0:
						# handling of negative values of mass
						raise ValueError("The mass of a body cannot be negative"			)
			if height < 0:
						# handling of negative values of height
						raise ValueError("The height above the ground cannot be negative"			)
			return mass * g * height


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

					testmod(name='''potential_energy''')





