


'''simple docstring'''



from __future__ import annotations

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






class        UpperCamelCase__(   SCREAMING_SNAKE_CASE__       ):




				@abstractmethod
				def __lt__(		self			: List[Any]      ,    lowerCAmelCase			: int      )->     bool:

										"""simple docstring"""




										pass




				@abstractmethod
				def __gt__(		self			: Union[str, Any]      ,    lowerCAmelCase			: Any      )->     bool:

										"""simple docstring"""




										pass





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

										"""simple docstring"""




										pass







_lowercase			:			Any	   =     TypeVar("""T""", bound=Comparable)






class        UpperCamelCase__(   Generic[T]       ):




				def __init__(		self			: Union[str, Any]      )->     None:

										"""simple docstring"""




										UpperCAmelCase     				=	[]
										UpperCAmelCase     				=	0




				def __repr__(		self			: List[Any]      )->     str:

										"""simple docstring"""




										return str(self.h      )




				def      a__(		self			: List[str]      ,    lowerCAmelCase			: Union[str, Any]      )->     int | None:

										"""simple docstring"""




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




				def      a__(		self			: Any      ,    lowerCAmelCase			: int      )->     int | None:

										"""simple docstring"""




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




				def      a__(		self			: Any      ,    lowerCAmelCase			: str      )->     int | None:

										"""simple docstring"""




										UpperCAmelCase     				=	2 * parent_idx + 2
										if right_child_index < self.heap_size:
																return right_child_index
										return None




				def      a__(		self			: Any      ,    lowerCAmelCase			: Any      )->     None:

										"""simple docstring"""




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




				def      a__(		self			: Optional[Any]      ,    lowerCAmelCase			: str      )->     None:

										"""simple docstring"""




										UpperCAmelCase     				=	list(_SCREAMING_SNAKE_CASE      )
										UpperCAmelCase     				=	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(_SCREAMING_SNAKE_CASE      )




				def      a__(		self			: List[Any]      )->     T:

										"""simple docstring"""




										if self.heap_size >= 2:
																UpperCAmelCase     				=	self.h[0]
																UpperCAmelCase     				=	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      a__(		self			: Union[str, Any]      ,    lowerCAmelCase			: Optional[Any]      )->     None:

										"""simple docstring"""




										self.h.append(_SCREAMING_SNAKE_CASE      )
										UpperCAmelCase     				=	(self.heap_size - 1) // 2
										self.heap_size += 1
										while idx >= 0:
																self.max_heapify(_SCREAMING_SNAKE_CASE      )
																UpperCAmelCase     				=	(idx - 1) // 2





				def      a__(		self			: Union[str, Any]      )->     None:

										"""simple docstring"""




										UpperCAmelCase     				=	self.heap_size
										for j in range(size - 1      ,    0      ,    -1      ):
																UpperCAmelCase     				=	self.h[j], self.h[0]
																self.heap_size -= 1
																self.max_heapify(0      )
										UpperCAmelCase     				=	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[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(100)
		print(F"""after new value 100 inserted: {heap}""")

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













from __future__ import annotations

def    lowerCAmelCase__		(			_a				:	list[int]     ,					_a				:	int			):
		snake_case_       ,				snake_case_ :							Tuple         =				0, len(_a			) - 1
		while start_ind <= end_ind:
				if array[start_ind] == search_item:
						return start_ind
				elif array[end_ind] == search_item:
						return end_ind
				else:
						start_ind += 1
						end_ind -= 1
    # returns -1 if search_item is not found in array
		return -1


if __name__ == "__main__":
							print(double_linear_search(list(range(1_00)), 40))
