
"""simple docstring"""


class 					lowerCAmelCase_					:



						'''simple docstring'''


						def __init__(			self  :   Union[str, Any]	,A_  :   Union[str, Any]	,A_  :   List[Any]   )  -> Union[str, Any]:
							A     = name
							A     = val


						def __str__(			self  :   Dict   )  -> Tuple:
							return F'{self.__class__.__name__}({self.name}, {self.val})'




						def __lt__(			self  :   Union[str, Any]	,A_  :   List[str]   )  -> str:
							return self.val < other.val







class 					lowerCAmelCase_					:



						'''simple docstring'''


						def __init__(			self  :   Optional[int]	,A_  :   Union[str, Any]   )  -> List[str]:
							A     = {}
							A     = {}
							A     = self.build_heap(A_   )


						def __getitem__(			self  :   str	,A_  :   Dict   )  -> Tuple:
							return self.get_value(A_   )


						def     _SCREAMING_SNAKE_CASE   (			self  :   int	,A_  :   Optional[int]   )  -> List[Any]:
							return (idx - 1) // 2


						def     _SCREAMING_SNAKE_CASE   (			self  :   int	,A_  :   Tuple   )  -> Union[str, Any]:
							return idx * 2 + 1


						def     _SCREAMING_SNAKE_CASE   (			self  :   int	,A_  :   Any   )  -> Tuple:
							return idx * 2 + 2


						def     _SCREAMING_SNAKE_CASE   (			self  :   int	,A_  :   Tuple   )  -> Any:
							return self.heap_dict[key]


						def     _SCREAMING_SNAKE_CASE   (			self  :   Tuple	,A_  :   Any   )  -> int:
							A     = len(A_   ) - 1
							A     = self.get_parent_idx(A_   )

							for idx, i in enumerate(A_   ):
								A     = idx
								A     = i.val

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


						def     _SCREAMING_SNAKE_CASE   (			self  :   List[str]	,A_  :   Union[str, Any]	,A_  :   Tuple   )  -> int:
							while True:
								A     = self.get_left_child_idx(A_   )  # noqa: E741
								A     = self.get_right_child_idx(A_   )

								A     = idx
								if l < len(A_   ) and array[l] < array[idx]:
									A     = l
								if r < len(A_   ) and array[r] < array[smallest]:
									A     = r

								if smallest != idx:
									A ,   A     = array[smallest], array[idx]
									(
									    (
									    A
									) ,   (
									    A
									) ,   
									)     = (
									    self.idx_of_element[array[smallest]],
									    self.idx_of_element[array[idx]],
									)
									A     = smallest
								else:
									break


						def     _SCREAMING_SNAKE_CASE   (			self  :   List[Any]	,A_  :   Any   )  -> Tuple:
							A     = self.get_parent_idx(A_   )
							while p >= 0 and self.heap[p] > self.heap[idx]:
								A ,   A     = self.heap[idx], self.heap[p]
								A ,   A     = (
								    self.idx_of_element[self.heap[idx]],
								    self.idx_of_element[self.heap[p]],
								)
								A     = p
								A     = self.get_parent_idx(A_   )


						def     _SCREAMING_SNAKE_CASE   (			self  :   Optional[Any]   )  -> Tuple:
							return self.heap[0]


						def     _SCREAMING_SNAKE_CASE   (			self  :   List[str]   )  -> int:
							A ,   A     = self.heap[-1], self.heap[0]
							A ,   A     = (
							    self.idx_of_element[self.heap[-1]],
							    self.idx_of_element[self.heap[0]],
							)

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


						def     _SCREAMING_SNAKE_CASE   (			self  :   List[Any]	,A_  :   Optional[int]   )  -> Optional[int]:
							self.heap.append(A_   )
							A     = len(self.heap   ) - 1
							A     = node.val
							self.sift_up(len(self.heap   ) - 1   )


						def     _SCREAMING_SNAKE_CASE   (			self  :   Union[str, Any]   )  -> List[str]:
							return len(self.heap   ) == 0




						def     _SCREAMING_SNAKE_CASE   (			self  :   int	,A_  :   Union[str, Any]	,A_  :   Optional[int]   )  -> List[Any]:
							assert (
							    self.heap[self.idx_of_element[node]].val > new_value
							), "newValue must be less that current value"
							A     = new_value
							A     = new_value
							self.sift_up(self.idx_of_element[node]   )

_lowercase				 =					Node('''R''', -1)
_lowercase				 =					Node('''B''', 6)
_lowercase				 =					Node('''A''', 3)
_lowercase				 =					Node('''X''', 1)
_lowercase				 =					Node('''E''', 4)

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

# Generating Min-Heap from array
_lowercase				 =					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()






# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

__lowerCamelCase			:	str					    =	TypeVar("""T""")



class    A__  (			Generic[T]     ):





      def __init__(					self			,				A_ = True  ):
       '''simple docstring'''




       UpperCamelCase      :   dict[T, list[T]]			      =  {}  # dictionary of lists
       UpperCamelCase      :   Union[str, Any]			      =  directed





      def 			__UpperCamelCase(					self			,				A_			,				A_  ):
       '''simple docstring'''




       if not self.directed:  # For undirected graphs
        # if both source vertex and destination vertex are both present in the
        # adjacency list, add destination vertex to source vertex list of adjacent
        # vertices and add source vertex to destination vertex list of adjacent
        # vertices.
        if source_vertex in self.adj_list and destination_vertex in self.adj_list:
         self.adj_list[source_vertex].append(A_  )
         self.adj_list[destination_vertex].append(A_  )
        # if only source vertex is present in adjacency list, add destination vertex
        # to source vertex list of adjacent vertices, then create a new vertex with
        # destination vertex as key and assign a list containing the source vertex
        # as it's first adjacent vertex.
        elif source_vertex in self.adj_list:
         self.adj_list[source_vertex].append(A_  )
         UpperCamelCase      :   Any			      =  [source_vertex]
        # if only destination vertex is present in adjacency list, add source vertex
        # to destination vertex list of adjacent vertices, then create a new vertex
        # with source vertex as key and assign a list containing the source vertex
        # as it's first adjacent vertex.
        elif destination_vertex in self.adj_list:
         self.adj_list[destination_vertex].append(A_  )
         UpperCamelCase      :   Any			      =  [destination_vertex]
        # if both source vertex and destination vertex are not present in adjacency
        # list, create a new vertex with source vertex as key and assign a list
        # containing the destination vertex as it's first adjacent vertex also
        # create a new vertex with destination vertex as key and assign a list
        # containing the source vertex as it's first adjacent vertex.
        else:
         UpperCamelCase      :   Union[str, Any]			      =  [destination_vertex]
         UpperCamelCase      :   List[str]			      =  [source_vertex]
       else:  # For directed graphs
        # if both source vertex and destination vertex are present in adjacency
        # list, add destination vertex to source vertex list of adjacent vertices.
        if source_vertex in self.adj_list and destination_vertex in self.adj_list:
         self.adj_list[source_vertex].append(A_  )
        # if only source vertex is present in adjacency list, add destination
        # vertex to source vertex list of adjacent vertices and create a new vertex
        # with destination vertex as key, which has no adjacent vertex
        elif source_vertex in self.adj_list:
         self.adj_list[source_vertex].append(A_  )
         UpperCamelCase      :   List[str]			      =  []
        # if only destination vertex is present in adjacency list, create a new
        # vertex with source vertex as key and assign a list containing destination
        # vertex as first adjacent vertex
        elif destination_vertex in self.adj_list:
         UpperCamelCase      :   Union[str, Any]			      =  [destination_vertex]
        # if both source vertex and destination vertex are not present in adjacency
        # list, create a new vertex with source vertex as key and a list containing
        # destination vertex as it's first adjacent vertex. Then create a new vertex
        # with destination vertex as key, which has no adjacent vertex
        else:
         UpperCamelCase      :   Union[str, Any]			      =  [destination_vertex]
         UpperCamelCase      :   Dict			      =  []

       return self





      def __repr__(					self  ):
       '''simple docstring'''




       return pformat(self.adj_list  )
