

"""simple docstring"""

from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar
class     A__      (      _a     ):




	@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

UpperCamelCase__ :    int 					=							TypeVar("T", bound=Comparable)
class     A__      (      Generic[T]     ):




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




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




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




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




	def 							a_		(   self  :	Tuple      ,    lowercase  :	int	)					-> int | None:
						__snake_case          =	2 * parent_idx + 2
						if right_child_index < self.heap_size:
											return right_child_index
						return None




	def 							a_		(   self  :	str      ,    lowercase  :	int	)					-> None:
						if index < self.heap_size:
											__snake_case          =	index
											__snake_case          =	self.left_child_idx(lowercase	)
											__snake_case          =	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]:
																__snake_case          =	left_child
											if right_child is not None and self.h[right_child] > self.h[violation]:
																__snake_case          =	right_child
											# if violation indeed exists
											if violation != index:
																# swap to fix the violation
																__snake_case      ,      __snake_case          =	self.h[index], self.h[violation]
																# fix the subsequent violation recursively if any
																self.max_heapify(lowercase	)




	def 							a_		(   self  :	int      ,    lowercase  :	Iterable[T]	)					-> None:
						__snake_case          =	list(lowercase	)
						__snake_case          =	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 							a_		(   self  :	Any	)					-> T:
						if self.heap_size >= 2:
											__snake_case          =	self.h[0]
											__snake_case          =	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  :	Dict      ,    lowercase  :	T	)					-> None:
						self.h.append(lowercase	)
						__snake_case          =	(self.heap_size - 1) // 2
						self.heap_size += 1
						while idx >= 0:
											self.max_heapify(lowercase	)
											__snake_case          =	(idx - 1) // 2




	def 							a_		(   self  :	int	)					-> None:
						__snake_case          =	self.heap_size
						for j in range(size - 1      ,    0      ,    -1	):
											__snake_case      ,      __snake_case          =	self.h[j], self.h[0]
											self.heap_size -= 1
											self.max_heapify(0	)
						__snake_case          =	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}')

				UpperCamelCase__ :    Tuple 					=							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"""

import functools
from math import sqrt
from time import time




def       snake_case__	(       lowerCAmelCase   :		int				,					*lowerCAmelCase   :		str				,					**lowerCAmelCase   :		List[Any]		):
					__snake_case          =	time()
					__snake_case          =	func(*lowerCAmelCase				,					**lowerCAmelCase		)
					__snake_case          =	time()
					if int(end - start		) > 0:
										print(F'''{func.__name__} runtime: {(end - start):0.4f} s'''		)
					else:
										print(F'''{func.__name__} runtime: {(end - start) * 1_000:0.4f} ms'''		)
					return output




def       snake_case__	(       lowerCAmelCase   :		int		):
					if n < 0:
										raise Exception("""n is negative"""		)
					if n == 0:
										return [0]
					__snake_case          =	[0, 1]
					for _ in range(n - 1		):
										fib.append(fib[-1] + fib[-2]		)
					return fib




def       snake_case__	(       lowerCAmelCase   :		int		):

					def fib_recursive_term(lowerCAmelCase   :		int		) -> int:
										if i < 0:
															raise Exception("""n is negative"""		)
										if i < 2:
															return i
										return fib_recursive_term(i - 1		) + fib_recursive_term(i - 2		)

					if n < 0:
										raise Exception("""n is negative"""		)
					return [fib_recursive_term(lowerCAmelCase		) for i in range(n + 1		)]




def       snake_case__	(       lowerCAmelCase   :		int		):

					@functools.cache
					def fib_recursive_term(lowerCAmelCase   :		int		) -> int:
										if i < 0:
															raise Exception("""n is negative"""		)
										if i < 2:
															return i
										return fib_recursive_term(i - 1		) + fib_recursive_term(i - 2		)

					if n < 0:
										raise Exception("""n is negative"""		)
					return [fib_recursive_term(lowerCAmelCase		) for i in range(n + 1		)]




def       snake_case__	(       lowerCAmelCase   :		int		):
					if n < 0:
										raise Exception("""n is negative"""		)
					# Cache must be outside recursuive function
					# other it will reset every time it calls itself.
					__snake_case          =	{0: 0, 1: 1, 2: 1}  # Prefilled cache

					def rec_fn_memoized(lowerCAmelCase   :		int		) -> int:
										if num in cache:
															return cache[num]

										__snake_case          =	rec_fn_memoized(num - 1		) + rec_fn_memoized(num - 2		)
										__snake_case          =	value
										return value

					return [rec_fn_memoized(lowerCAmelCase		) for i in range(n + 1		)]




def       snake_case__	(       lowerCAmelCase   :		int		):
					if n < 0:
										raise Exception("""n is negative"""		)
					if n >= 1_475:
										raise Exception("""n is too large"""		)
					__snake_case          =	sqrt(5		)
					__snake_case          =	(1 + sqrt_a) / 2
					return [round(phi**i / sqrt_a		) for i in range(n + 1		)]


if __name__ == "__main__":
		UpperCamelCase__ :    Optional[Any] 					=							30
		time_func(fib_iterative, num)
		time_func(fib_recursive, num)  # Around 3s runtime
		time_func(fib_recursive_cached, num)  # Around 0ms runtime
		time_func(fib_memoization, num)
		time_func(fib_binet, num)


