


'''simple docstring'''






class 						__UpperCamelCase	:





							def __init__(  self		:List[Any]  ,_UpperCamelCase		:Optional[Any]  ,_UpperCamelCase		:List[str]			):
									snake_case_		:							int			       =						name
									snake_case_		:							Tuple			       =						val





							def __str__(  self		:Optional[int]			):
									return F'''{self.__class__.__name__}({self.name}, {self.val})'''





							def __lt__(  self		:int  ,_UpperCamelCase		:List[Any]			):
									return self.val < other.val





class 						__UpperCamelCase	:





							def __init__(  self		:List[str]  ,_UpperCamelCase		:Any			):
									snake_case_		:							Union[str, Any]			       =						{}
									snake_case_		:							Union[str, Any]			       =						{}
									snake_case_		:							List[str]			       =						self.build_heap(_UpperCamelCase			)





							def __getitem__(  self		:Dict  ,_UpperCamelCase		:Dict			):
									return self.get_value(_UpperCamelCase			)





							def 		a__   (  self		:Dict  ,_UpperCamelCase		:str			):
									return (idx - 1) // 2





							def 		a__   (  self		:List[Any]  ,_UpperCamelCase		:Dict			):
									return idx * 2 + 1





							def 		a__   (  self		:List[str]  ,_UpperCamelCase		:Tuple			):
									return idx * 2 + 2





							def 		a__   (  self		:Union[str, Any]  ,_UpperCamelCase		:Any			):
									return self.heap_dict[key]





							def 		a__   (  self		:Optional[Any]  ,_UpperCamelCase		:Tuple			):
									snake_case_		:							Tuple			       =						len(_UpperCamelCase			) - 1
									snake_case_		:							int			       =						self.get_parent_idx(_UpperCamelCase			)

									for idx, i in enumerate(_UpperCamelCase			):
											snake_case_		:							Optional[int]			       =						idx
											snake_case_		:							List[Any]			       =						i.val

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





							def 		a__   (  self		:List[Any]  ,_UpperCamelCase		:Tuple  ,_UpperCamelCase		:Optional[int]			):
									while True:
											snake_case_		:							Union[str, Any]			       =						self.get_left_child_idx(_UpperCamelCase			)  # noqa: E741
											snake_case_		:							List[str]			       =						self.get_right_child_idx(_UpperCamelCase			)

											snake_case_		:							Tuple			       =						idx
											if l < len(_UpperCamelCase			) and array[l] < array[idx]:
													snake_case_		:							List[Any]			       =						l
											if r < len(_UpperCamelCase			) and array[r] < array[smallest]:
													snake_case_		:							str			       =						r

											if smallest != idx:
													snake_case_       ,      snake_case_		:							List[Any]			       =						array[smallest], array[idx]
													(
													    (
													    snake_case_
													)       ,      (
													    snake_case_
													)       ,      
													)		:							Optional[int]			       =						(
													    self.idx_of_element[array[smallest]],
													    self.idx_of_element[array[idx]],
													)
													snake_case_		:							str			       =						smallest
											else:
													break





							def 		a__   (  self		:Tuple  ,_UpperCamelCase		:Any			):
									snake_case_		:							List[str]			       =						self.get_parent_idx(_UpperCamelCase			)
									while p >= 0 and self.heap[p] > self.heap[idx]:
											snake_case_       ,      snake_case_		:							Union[str, Any]			       =						self.heap[idx], self.heap[p]
											snake_case_       ,      snake_case_		:							Any			       =						(
											    self.idx_of_element[self.heap[idx]],
											    self.idx_of_element[self.heap[p]],
											)
											snake_case_		:							Dict			       =						p
											snake_case_		:							int			       =						self.get_parent_idx(_UpperCamelCase			)





							def 		a__   (  self		:Optional[int]			):
									return self.heap[0]





							def 		a__   (  self		:int			):
									snake_case_       ,      snake_case_		:							Tuple			       =						self.heap[-1], self.heap[0]
									snake_case_       ,      snake_case_		:							Union[str, Any]			       =						(
									    self.idx_of_element[self.heap[-1]],
									    self.idx_of_element[self.heap[0]],
									)

									snake_case_		:							List[Any]			       =						self.heap.pop()
									del self.idx_of_element[x]
									self.sift_down(0  ,self.heap			)
									return x





							def 		a__   (  self		:int  ,_UpperCamelCase		:List[Any]			):
									self.heap.append(_UpperCamelCase			)
									snake_case_		:							List[str]			       =						len(self.heap			) - 1
									snake_case_		:							List[Any]			       =						node.val
									self.sift_up(len(self.heap			) - 1			)





							def 		a__   (  self		:Union[str, Any]			):
									return len(self.heap			) == 0





							def 		a__   (  self		:List[str]  ,_UpperCamelCase		:Optional[int]  ,_UpperCamelCase		:str			):
									assert (
									    self.heap[self.idx_of_element[node]].val > new_value
									), "newValue must be less that current value"
									snake_case_		:							Dict			       =						new_value
									snake_case_		:							List[Any]			       =						new_value
									self.sift_up(self.idx_of_element[node]			)





__A	:	Optional[int]     =     Node('R', -1)
__A	:	int     =     Node('B', 6)
__A	:	List[Any]     =     Node('A', 3)
__A	:	Tuple     =     Node('X', 1)
__A	:	int     =     Node('E', 4)

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

# Generating Min-Heap from array
__A	:	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, -17)

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

if __name__ == "__main__":
							import doctest

							doctest.testmod()



'''simple docstring'''






import random
from typing import Any





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







		'''simple docstring'''
		for _ in range(len(lowerCamelCase_ ) ):
				snake_case_		:							Union[str, Any]			       =						random.randint(0				,      len(lowerCamelCase_ ) - 1 )
				snake_case_		:							Any			       =						random.randint(0				,      len(lowerCamelCase_ ) - 1 )
				snake_case_       ,      snake_case_		:							List[str]			       =						data[b], data[a]
		return data


if __name__ == "__main__":
							__A	:	Optional[int]     =     [0, 1, 2, 3, 4, 5, 6, 7]
							__A	:	Optional[int]     =     ['python', 'says', 'hello', '!']
							print('Fisher-Yates Shuffle:')
							print('List', integers, strings)
							print('FY Shuffle', fisher_yates_shuffle(integers), fisher_yates_shuffle(strings))