




class  _lowerCAmelCase     :

      def __init__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Tuple		       =     name
        lowerCAmelCase__				:  List[str]		       =     val

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







      def __lt__(   self      ,				__UpperCAmelCase		):
        return self.val < other.val






class  _lowerCAmelCase     :

      def __init__(   self      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Dict		       =     {}
        lowerCAmelCase__				:  Any		       =     {}
        lowerCAmelCase__				:  Tuple		       =     self.build_heap(lowerCamelCase__		)

      def __getitem__(   self      ,				__UpperCAmelCase		):
        return self.get_value(lowerCamelCase__		)

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        return (idx - 1) // 2

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        return idx * 2 + 1

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        return idx * 2 + 2

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        return self.heap_dict[key]

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Union[str, Any]		       =     len(lowerCamelCase__		) - 1
        lowerCAmelCase__				:  List[str]		       =     self.get_parent_idx(lowerCamelCase__		)

        for idx, i in enumerate(lowerCamelCase__		):
          lowerCAmelCase__				:  List[str]		       =     idx
          lowerCAmelCase__				:  Tuple		       =     i.val

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

      def 	__magic_name__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):







        while True:
          lowerCAmelCase__				:  List[Any]		       =     self.get_left_child_idx(lowerCamelCase__		)  # noqa: E741
          lowerCAmelCase__				:  Dict		       =     self.get_right_child_idx(lowerCamelCase__		)

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

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

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  List[str]		       =     self.get_parent_idx(lowerCamelCase__		)
        while p >= 0 and self.heap[p] > self.heap[idx]:
          lowerCAmelCase__				:  Optional[int]		       =     self.heap[idx], self.heap[p]
          lowerCAmelCase__				:  Dict		       =     (
              self.idx_of_element[self.heap[idx]],
              self.idx_of_element[self.heap[p]],
          )
          lowerCAmelCase__				:  Optional[int]		       =     p
          lowerCAmelCase__				:  str		       =     self.get_parent_idx(lowerCamelCase__		)

      def 	__magic_name__(   self		):
        return self.heap[0]

      def 	__magic_name__(   self		):
        lowerCAmelCase__				:  Dict		       =     self.heap[-1], self.heap[0]
        lowerCAmelCase__				:  Tuple		       =     (
            self.idx_of_element[self.heap[-1]],
            self.idx_of_element[self.heap[0]],
        )

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

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        self.heap.append(lowerCamelCase__		)
        lowerCAmelCase__				:  int		       =     len(self.heap		) - 1
        lowerCAmelCase__				:  int		       =     node.val
        self.sift_up(len(self.heap		) - 1		)

      def 	__magic_name__(   self		):
        return len(self.heap		) == 0







      def 	__magic_name__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):
        assert (
            self.heap[self.idx_of_element[node]].val > new_value
        ), "newValue must be less that current value"
        lowerCAmelCase__				:  int		       =     new_value
        lowerCAmelCase__				:  Union[str, Any]		       =     new_value
        self.sift_up(self.idx_of_element[node]		)
lowerCAmelCase_					    = Node("""R""", -1)
lowerCAmelCase_					    = Node("""B""", 6)
lowerCAmelCase_					    = Node("""A""", 3)
lowerCAmelCase_					    = Node("""X""", 1)
lowerCAmelCase_					    = Node("""E""", 4)

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

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







def      __lowerCAmelCase			(					UpperCamelCase      )     ->	None:
  lowerCAmelCase__				:  Dict		       =     generate_pascal_triangle(UpperCamelCase      )
  for row_idx in range(UpperCamelCase      ):
    # Print left spaces
    for _ in range(num_rows - row_idx - 1      ):
      print(end=''' '''      )
    # Print row values
    for col_idx in range(row_idx + 1      ):
      if col_idx != row_idx:
        print(triangle[row_idx][col_idx]	,      end=''' '''      )
      else:
        print(triangle[row_idx][col_idx]	,      end=''''''      )
    print()



def      __lowerCAmelCase			(					UpperCamelCase      )     ->	list[list[int]]:

  if not isinstance(UpperCamelCase	,      UpperCamelCase      ):
    raise TypeError('''The input value of \'num_rows\' should be \'int\''''      )

  if num_rows == 0:
    return []
  elif num_rows < 0:
    raise ValueError(
        '''The input value of \'num_rows\' should be greater than or equal to 0'''      )

  lowerCAmelCase__				:  list[list[int]]		       =     []
  for current_row_idx in range(UpperCamelCase      ):
    lowerCAmelCase__				:  List[str]		       =     populate_current_row(UpperCamelCase	,      UpperCamelCase      )
    triangle.append(UpperCamelCase      )
  return triangle



def      __lowerCAmelCase			(					UpperCamelCase	,      UpperCamelCase      )     ->	list[int]:
  lowerCAmelCase__				:  Optional[Any]		       =     [-1] * (current_row_idx + 1)
  # first and last elements of current row are equal to 1
  lowerCAmelCase__       ,			lowerCAmelCase__				:  int		       =     1, 1
  for current_col_idx in range(1	,      UpperCamelCase      ):
    calculate_current_element(
        UpperCamelCase	,      UpperCamelCase	,      UpperCamelCase	,      UpperCamelCase      )
  return current_row



def      __lowerCAmelCase			(					UpperCamelCase	,      UpperCamelCase	,      UpperCamelCase	,      UpperCamelCase	,      )     ->	None:
  lowerCAmelCase__				:  Optional[int]		       =     triangle[current_row_idx - 1][current_col_idx - 1]
  lowerCAmelCase__				:  List[str]		       =     triangle[current_row_idx - 1][current_col_idx]
  lowerCAmelCase__				:  List[Any]		       =     above_to_left_elt + above_to_right_elt



def      __lowerCAmelCase			(					UpperCamelCase      )     ->	list[list[int]]:

  if not isinstance(UpperCamelCase	,      UpperCamelCase      ):
    raise TypeError('''The input value of \'num_rows\' should be \'int\''''      )

  if num_rows == 0:
    return []
  elif num_rows < 0:
    raise ValueError(
        '''The input value of \'num_rows\' should be greater than or equal to 0'''      )

  lowerCAmelCase__				:  list[list[int]]		       =     [[1]]

  for row_index in range(1	,      UpperCamelCase      ):
    lowerCAmelCase__				:  Optional[int]		       =     [0] + result[-1] + [0]
    lowerCAmelCase__				:  List[str]		       =     row_index + 1
    # Calculate the number of distinct elements in a row
    lowerCAmelCase__				:  Tuple		       =     sum(divmod(UpperCamelCase	,      2      )      )
    lowerCAmelCase__				:  Tuple		       =     [
        temp_row[i - 1] + temp_row[i] for i in range(1	,      distinct_elements + 1      )
    ]
    lowerCAmelCase__				:  int		       =     row_first_half[: (row_index + 1) // 2]
    row_second_half.reverse()
    lowerCAmelCase__				:  Dict		       =     row_first_half + row_second_half
    result.append(UpperCamelCase      )

  return result



def      __lowerCAmelCase			(					)     ->	None:
  from collections.abc import Callable
  from timeit import timeit

  def benchmark_a_function(UpperCamelCase	,      UpperCamelCase      ) -> None:
    lowerCAmelCase__				:  Tuple		       =     F"""{func.__name__}({value})"""
    lowerCAmelCase__				:  Dict		       =     timeit(F"""__main__.{call}"""	,      setup='''import __main__'''      )
    # print(f"{call:38} = {func(value)} -- {timing:.4f} seconds")
    print(F"""{call:38} -- {timing:.4f} seconds"""      )

  for value in range(15      ):  # (1, 7, 14):
    for func in (generate_pascal_triangle, generate_pascal_triangle_optimized):
      benchmark_a_function(UpperCamelCase	,      UpperCamelCase      )
    print()


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     benchmark()

