



class  lowerCamelCase__    :




		'''simple docstring'''



		def __init__(self	,__lowerCamelCase	,__lowerCamelCase				)  ->    List[Any]:

						"""simple docstring"""






						lowerCAmelCase__  :       int				=  name
						lowerCAmelCase__  :       Any				=  val



		def __str__(self				)  ->    Optional[int]:

						"""simple docstring"""






						return f"""{self.__class__.__name__}({self.name}, {self.val})"""



		def __lt__(self	,__lowerCamelCase				)  ->    List[Any]:

						"""simple docstring"""






						return self.val < other.val



class  lowerCamelCase__    :




		'''simple docstring'''



		def __init__(self	,__lowerCamelCase				)  ->    Optional[int]:

						"""simple docstring"""






						lowerCAmelCase__  :       Optional[Any]				=  {}
						lowerCAmelCase__  :       Union[str, Any]				=  {}
						lowerCAmelCase__  :       Optional[int]				=  self.build_heap(__lowerCamelCase				)



		def __getitem__(self	,__lowerCamelCase				)  ->    Union[str, Any]:

						"""simple docstring"""






						return self.get_value(__lowerCamelCase				)



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    Union[str, Any]:

						"""simple docstring"""






						return (idx - 1) // 2



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    List[str]:

						"""simple docstring"""






						return idx * 2 + 1



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    List[str]:

						"""simple docstring"""






						return idx * 2 + 2



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    int:

						"""simple docstring"""






						return self.heap_dict[key]



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    List[str]:

						"""simple docstring"""






						lowerCAmelCase__  :       int				=  len(__lowerCamelCase				) - 1
						lowerCAmelCase__  :       Tuple				=  self.get_parent_idx(__lowerCamelCase				)

						for idx, i in enumerate(__lowerCamelCase				):
										lowerCAmelCase__  :       Dict				=  idx
										lowerCAmelCase__  :       Dict				=  i.val

						for i in range(__lowerCamelCase	,-1	,-1				):
										self.sift_down(__lowerCamelCase	,__lowerCamelCase				)
						return array



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase				)  ->    Union[str, Any]:

						"""simple docstring"""






						while True:
										lowerCAmelCase__  :       Dict				=  self.get_left_child_idx(__lowerCamelCase				)  # noqa: E741
										lowerCAmelCase__  :       Any				=  self.get_right_child_idx(__lowerCamelCase				)

										lowerCAmelCase__  :       str				=  idx
										if l < len(__lowerCamelCase				) and array[l] < array[idx]:
														lowerCAmelCase__  :       Optional[int]				=  l
										if r < len(__lowerCamelCase				) and array[r] < array[smallest]:
														lowerCAmelCase__  :       str				=  r

										if smallest != idx:
														lowerCAmelCase__		,	lowerCAmelCase__  :       Optional[int]				=  array[smallest], array[idx]
														(
														    (
														    lowerCAmelCase__
														)		,	(
														    lowerCAmelCase__
														)		,	
														)  :       Tuple				=  (
														    self.idx_of_element[array[smallest]],
														    self.idx_of_element[array[idx]],
														)
														lowerCAmelCase__  :       Optional[int]				=  smallest
										else:
														break



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    List[Any]:

						"""simple docstring"""






						lowerCAmelCase__  :       Dict				=  self.get_parent_idx(__lowerCamelCase				)
						while p >= 0 and self.heap[p] > self.heap[idx]:
										lowerCAmelCase__		,	lowerCAmelCase__  :       Optional[Any]				=  self.heap[idx], self.heap[p]
										lowerCAmelCase__		,	lowerCAmelCase__  :       List[Any]				=  (
										    self.idx_of_element[self.heap[idx]],
										    self.idx_of_element[self.heap[p]],
										)
										lowerCAmelCase__  :       Dict				=  p
										lowerCAmelCase__  :       int				=  self.get_parent_idx(__lowerCamelCase				)



		def 	lowerCAmelCase__   (self				)  ->    Any:

						"""simple docstring"""






						return self.heap[0]



		def 	lowerCAmelCase__   (self				)  ->    str:

						"""simple docstring"""






						lowerCAmelCase__		,	lowerCAmelCase__  :       Union[str, Any]				=  self.heap[-1], self.heap[0]
						lowerCAmelCase__		,	lowerCAmelCase__  :       Union[str, Any]				=  (
						    self.idx_of_element[self.heap[-1]],
						    self.idx_of_element[self.heap[0]],
						)

						lowerCAmelCase__  :       str				=  self.heap.pop()
						del self.idx_of_element[x]
						self.sift_down(0	,self.heap				)
						return x



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    List[str]:

						"""simple docstring"""






						self.heap.append(__lowerCamelCase				)
						lowerCAmelCase__  :       Tuple				=  len(self.heap				) - 1
						lowerCAmelCase__  :       str				=  node.val
						self.sift_up(len(self.heap				) - 1				)



		def 	lowerCAmelCase__   (self				)  ->    Dict:

						"""simple docstring"""






						return len(self.heap				) == 0



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase				)  ->    str:

						"""simple docstring"""






						assert (
						    self.heap[self.idx_of_element[node]].val > new_value
						), "newValue must be less that current value"
						lowerCAmelCase__  :       int				=  new_value
						lowerCAmelCase__  :       Tuple				=  new_value
						self.sift_up(self.idx_of_element[node]				)


__snake_case       :	Optional[Any]            =Node('R', -1)
__snake_case       :	Dict            =Node('B', 6)
__snake_case       :	List[Any]            =Node('A', 3)
__snake_case       :	List[Any]            =Node('X', 1)
__snake_case       :	Union[str, Any]            =Node('E', 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
__snake_case       :	Any            =MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print('Min Heap - before decrease key')
for i in my_min_heap.heap:
							print(i)

print('Min Heap - After decrease key of node [B -> -17]')
my_min_heap.decrease_key(b, -1_7)

# After
for i in my_min_heap.heap:
							print(i)

if __name__ == "__main__":
							import doctest

							doctest.testmod()






def 			lowerCAmelCase__	(					lowerCamelCase_	:	int):





				'''simple docstring'''

				if length <= 0 or not isinstance(lowerCamelCase_ ,lowerCamelCase_):
								raise ValueError('''Length must be a positive integer.''')
				return [n * (2 * n - 1) for n in range(lowerCamelCase_)]


if __name__ == "__main__":
							print(hexagonal_numbers(length=5))
							print(hexagonal_numbers(length=1_0))

