

'''simple docstring'''

class 				_snake_case			:
   def __init__(			self      :   Any  ,SCREAMING_SNAKE_CASE__      :   Any  ,SCREAMING_SNAKE_CASE__      :   Any				):
     SCREAMING_SNAKE_CASE:List[Any]       =       name
     SCREAMING_SNAKE_CASE:Tuple       =       val
   def __str__(			self      :   Union[str, Any]				):
     return F'''{self.__class__.__name__}({self.name}, {self.val})'''







   def __lt__(			self      :   List[str]  ,SCREAMING_SNAKE_CASE__      :   Dict				):
     return self.val < other.val





class 				_snake_case			:
   def __init__(			self      :   str  ,SCREAMING_SNAKE_CASE__      :   Optional[Any]				):
     SCREAMING_SNAKE_CASE:Optional[int]       =       {}
     SCREAMING_SNAKE_CASE:Optional[int]       =       {}
     SCREAMING_SNAKE_CASE:Dict       =       self.build_heap(lowerCAmelCase_				)
   def __getitem__(			self      :   Dict  ,SCREAMING_SNAKE_CASE__      :   int				):
     return self.get_value(lowerCAmelCase_				)
   def      __UpperCamelCase    (			self      :   Tuple  ,SCREAMING_SNAKE_CASE__      :   List[Any]				):
     return (idx - 1) // 2
   def      __UpperCamelCase    (			self      :   Dict  ,SCREAMING_SNAKE_CASE__      :   str				):
     return idx * 2 + 1
   def      __UpperCamelCase    (			self      :   Any  ,SCREAMING_SNAKE_CASE__      :   Optional[int]				):
     return idx * 2 + 2
   def      __UpperCamelCase    (			self      :   Optional[int]  ,SCREAMING_SNAKE_CASE__      :   Optional[Any]				):
     return self.heap_dict[key]
   def      __UpperCamelCase    (			self      :   Any  ,SCREAMING_SNAKE_CASE__      :   List[Any]				):
     SCREAMING_SNAKE_CASE:Any       =       len(lowerCAmelCase_				) - 1
     SCREAMING_SNAKE_CASE:List[str]       =       self.get_parent_idx(lowerCAmelCase_				)

     for idx, i in enumerate(lowerCAmelCase_				):
       SCREAMING_SNAKE_CASE:Any       =       idx
       SCREAMING_SNAKE_CASE:str       =       i.val

     for i in range(lowerCAmelCase_  ,-1  ,-1				):
       self.sift_down(lowerCAmelCase_  ,lowerCAmelCase_				)
     return array
   def      __UpperCamelCase    (			self      :   List[str]  ,SCREAMING_SNAKE_CASE__      :   str  ,SCREAMING_SNAKE_CASE__      :   Tuple				):
     while True:
       SCREAMING_SNAKE_CASE:Any       =       self.get_left_child_idx(lowerCAmelCase_				)  # noqa: E741
       SCREAMING_SNAKE_CASE:str       =       self.get_right_child_idx(lowerCAmelCase_				)

       SCREAMING_SNAKE_CASE:Tuple       =       idx
       if l < len(lowerCAmelCase_				) and array[l] < array[idx]:
         SCREAMING_SNAKE_CASE:Tuple       =       l
       if r < len(lowerCAmelCase_				) and array[r] < array[smallest]:
         SCREAMING_SNAKE_CASE:Union[str, Any]       =       r

       if smallest != idx:
         SCREAMING_SNAKE_CASE:int       =       array[smallest], array[idx]
         (
             SCREAMING_SNAKE_CASE						
         ):Any       =       (
             self.idx_of_element[array[smallest]],
             self.idx_of_element[array[idx]],
         )
         SCREAMING_SNAKE_CASE:List[Any]       =       smallest
       else:
         break
   def      __UpperCamelCase    (			self      :   List[Any]  ,SCREAMING_SNAKE_CASE__      :   Any				):
     SCREAMING_SNAKE_CASE:List[Any]       =       self.get_parent_idx(lowerCAmelCase_				)
     while p >= 0 and self.heap[p] > self.heap[idx]:
       SCREAMING_SNAKE_CASE:str       =       self.heap[idx], self.heap[p]
       SCREAMING_SNAKE_CASE:Optional[int]       =       (
           self.idx_of_element[self.heap[idx]],
           self.idx_of_element[self.heap[p]],
       )
       SCREAMING_SNAKE_CASE:str       =       p
       SCREAMING_SNAKE_CASE:int       =       self.get_parent_idx(lowerCAmelCase_				)
   def      __UpperCamelCase    (			self      :   Optional[Any]				):
     return self.heap[0]
   def      __UpperCamelCase    (			self      :   List[Any]				):
     SCREAMING_SNAKE_CASE:List[str]       =       self.heap[-1], self.heap[0]
     SCREAMING_SNAKE_CASE:Optional[Any]       =       (
         self.idx_of_element[self.heap[-1]],
         self.idx_of_element[self.heap[0]],
     )

     SCREAMING_SNAKE_CASE:Dict       =       self.heap.pop()
     del self.idx_of_element[x]
     self.sift_down(0  ,self.heap				)
     return x
   def      __UpperCamelCase    (			self      :   Dict  ,SCREAMING_SNAKE_CASE__      :   Optional[Any]				):
     self.heap.append(lowerCAmelCase_				)
     SCREAMING_SNAKE_CASE:int       =       len(self.heap				) - 1
     SCREAMING_SNAKE_CASE:List[Any]       =       node.val
     self.sift_up(len(self.heap				) - 1				)
   def      __UpperCamelCase    (			self      :   int				):
     return len(self.heap				) == 0







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



A_							    =				Node("R", -1)
A_							    =				Node("B", 6)
A_							    =				Node("A", 3)
A_							    =				Node("X", 1)
A_							    =				Node("E", 4)

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

# Generating Min-Heap from array
A_							    =				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"""
class _lowerCAmelCase						:







						def __init__(    self   ,				lowerCAmelCase_   ,				lowerCAmelCase_=None   ,				lowerCAmelCase_=None							)		->							int:
										_SCREAMING_SNAKE_CASE   :		Optional[int]       		=    data
										_SCREAMING_SNAKE_CASE   :		Tuple       		=    previous
										_SCREAMING_SNAKE_CASE   :		Any       		=    next_node







						def __str__(    self							)		->							str:
										return F"""{self.data}"""







						def 			A      (    self							)		->							int:
										return self.data







						def 			A      (    self							)		->							Dict:
										return self.next







						def 			A      (    self							)		->							Union[str, Any]:
										return self.previous







class _lowerCAmelCase						:







						def __init__(    self   ,				lowerCAmelCase_							)		->							List[str]:
										_SCREAMING_SNAKE_CASE   :		List[Any]       		=    head







						def __iter__(    self							)		->							Any:
										return self







						def 			A      (    self							)		->							Dict:
										if not self.current:
														raise StopIteration
										else:
														_SCREAMING_SNAKE_CASE   :		Any       		=    self.current.get_data()
														_SCREAMING_SNAKE_CASE   :		Dict       		=    self.current.get_next()
														return value







class _lowerCAmelCase						:







						def __init__(    self							)		->							Dict:
										_SCREAMING_SNAKE_CASE   :		Dict       		=    None  # First node in list
										_SCREAMING_SNAKE_CASE   :		Union[str, Any]       		=    None  # Last node in list







						def __str__(    self							)		->							Any:
										_SCREAMING_SNAKE_CASE   :		str       		=    self.head
										_SCREAMING_SNAKE_CASE   :		int       		=    []
										while current is not None:
														nodes.append(current.get_data()							)
														_SCREAMING_SNAKE_CASE   :		List[Any]       		=    current.get_next()
										return " ".join(str(lowerCAmelCase_							) for node in nodes							)







						def __contains__(    self   ,				lowerCAmelCase_							)		->							Any:
										_SCREAMING_SNAKE_CASE   :		Any       		=    self.head
										while current:
														if current.get_data() == value:
																		return True
														_SCREAMING_SNAKE_CASE   :		int       		=    current.get_next()
										return False







						def __iter__(    self							)		->							str:
										return LinkedListIterator(self.head							)







						def 			A      (    self							)		->							Dict:
										if self.head:
														return self.head.get_data()
										return None







						def 			A      (    self							)		->							List[Any]:
										if self.tail:
														return self.tail.get_data()
										return None







						def 			A      (    self   ,				lowerCAmelCase_							)		->							None:
										if self.head is None:
														_SCREAMING_SNAKE_CASE   :		List[Any]       		=    node
														_SCREAMING_SNAKE_CASE   :		Dict       		=    node
										else:
														self.insert_before_node(self.head   ,				lowerCAmelCase_							)







						def 			A      (    self   ,				lowerCAmelCase_							)		->							None:
										if self.head is None:
														self.set_head(lowerCAmelCase_							)
										else:
														self.insert_after_node(self.tail   ,				lowerCAmelCase_							)







						def 			A      (    self   ,				lowerCAmelCase_							)		->							None:
										_SCREAMING_SNAKE_CASE   :		Any       		=    Node(lowerCAmelCase_							)
										if self.head is None:
														self.set_head(lowerCAmelCase_							)
										else:
														self.set_tail(lowerCAmelCase_							)







						def 			A      (    self   ,				lowerCAmelCase_   ,				lowerCAmelCase_							)		->							None:
										_SCREAMING_SNAKE_CASE   :		Optional[Any]       		=    node
										_SCREAMING_SNAKE_CASE   :		List[Any]       		=    node.previous

										if node.get_previous() is None:
														_SCREAMING_SNAKE_CASE   :		List[Any]       		=    node_to_insert
										else:
														_SCREAMING_SNAKE_CASE   :		Optional[int]       		=    node_to_insert

										_SCREAMING_SNAKE_CASE   :		Any       		=    node_to_insert







						def 			A      (    self   ,				lowerCAmelCase_   ,				lowerCAmelCase_							)		->							None:
										_SCREAMING_SNAKE_CASE   :		Optional[Any]       		=    node
										_SCREAMING_SNAKE_CASE   :		Optional[int]       		=    node.next

										if node.get_next() is None:
														_SCREAMING_SNAKE_CASE   :		Tuple       		=    node_to_insert
										else:
														_SCREAMING_SNAKE_CASE   :		Any       		=    node_to_insert

										_SCREAMING_SNAKE_CASE   :		List[str]       		=    node_to_insert







						def 			A      (    self   ,				lowerCAmelCase_   ,				lowerCAmelCase_							)		->							None:
										_SCREAMING_SNAKE_CASE   :		List[Any]       		=    1
										_SCREAMING_SNAKE_CASE   :		str       		=    Node(lowerCAmelCase_							)
										_SCREAMING_SNAKE_CASE   :		Union[str, Any]       		=    self.head
										while node:
														if current_position == position:
																		self.insert_before_node(lowerCAmelCase_   ,				lowerCAmelCase_							)
																		return
														current_position += 1
														_SCREAMING_SNAKE_CASE   :		List[str]       		=    node.next
										self.insert_after_node(self.tail   ,				lowerCAmelCase_							)







						def 			A      (    self   ,				lowerCAmelCase_							)		->							Node:
										_SCREAMING_SNAKE_CASE   :		Tuple       		=    self.head
										while node:
														if node.get_data() == item:
																		return node
														_SCREAMING_SNAKE_CASE   :		Dict       		=    node.get_next()
										raise Exception('Node not found'							)







						def 			A      (    self   ,				lowerCAmelCase_							)		->							int:
										if (node := self.get_node(lowerCAmelCase_							)) is not None:
														if node == self.head:
																		_SCREAMING_SNAKE_CASE   :		Union[str, Any]       		=    self.head.get_next()

														if node == self.tail:
																		_SCREAMING_SNAKE_CASE   :		int       		=    self.tail.get_previous()

														self.remove_node_pointers(lowerCAmelCase_							)







						@staticmethod
						def 			A      (    lowerCAmelCase_							)		->							None:
										if node.get_next():
														_SCREAMING_SNAKE_CASE   :		List[Any]       		=    node.previous

										if node.get_previous():
														_SCREAMING_SNAKE_CASE   :		str       		=    node.next

										_SCREAMING_SNAKE_CASE   :		Optional[int]       		=    None
										_SCREAMING_SNAKE_CASE   :		List[Any]       		=    None







						def 			A      (    self							)		->							List[str]:
										return self.head is None







def 				lowercase__		(					):
				pass


if __name__ == "__main__":
			import doctest

			doctest.testmod()

