




class  lowerCamelCase_							:


 '''simple docstring'''







 def __init__(							self						:	List[Any]       ,       _lowerCAmelCase						:	int		):
       SCREAMING_SNAKE_CASE_					=    val
       # Number of nodes in left subtree
       SCREAMING_SNAKE_CASE_					=    0
       SCREAMING_SNAKE_CASE_					=    None
       SCREAMING_SNAKE_CASE_					=    None
       SCREAMING_SNAKE_CASE_					=    None




 def    lowerCAmelCase_						(							self						:	Optional[int]       ,       _lowerCAmelCase						:	List[Any]		):
       assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

       if self.val < other.val:
             SCREAMING_SNAKE_CASE_					=    self.right
             SCREAMING_SNAKE_CASE_					=    None
             if self.right:
                   SCREAMING_SNAKE_CASE_					=    other
             SCREAMING_SNAKE_CASE_					=    other
             SCREAMING_SNAKE_CASE_					=    self.left_tree_size * 2 + 1
             return self
       else:
             SCREAMING_SNAKE_CASE_					=    other.right
             SCREAMING_SNAKE_CASE_					=    None
             if other.right:
                   SCREAMING_SNAKE_CASE_					=    self
             SCREAMING_SNAKE_CASE_					=    self
             SCREAMING_SNAKE_CASE_					=    other.left_tree_size * 2 + 1
             return other





class  lowerCamelCase_							:


 '''simple docstring'''







 def __init__(							self						:	List[str]       ,       _lowerCAmelCase						:	Optional[int]=None       ,       _lowerCAmelCase						:	str=None       ,       _lowerCAmelCase						:	List[Any]=0		):
       SCREAMING_SNAKE_CASE_					=    heap_size
       SCREAMING_SNAKE_CASE_					=    bottom_root
       SCREAMING_SNAKE_CASE_					=    min_node



 def    lowerCAmelCase_						(							self						:	int       ,       _lowerCAmelCase						:	int		):

       # Empty heaps corner cases
       if other.size == 0:
             return None
       if self.size == 0:
             SCREAMING_SNAKE_CASE_					=    other.size
             SCREAMING_SNAKE_CASE_					=    other.bottom_root
             SCREAMING_SNAKE_CASE_					=    other.min_node
             return None
       # Update size
       SCREAMING_SNAKE_CASE_					=    self.size + other.size

       # Update min.node
       if self.min_node.val > other.min_node.val:
             SCREAMING_SNAKE_CASE_					=    other.min_node
       # Merge

       # Order roots by left_subtree_size
       SCREAMING_SNAKE_CASE_					=    []
       SCREAMING_SNAKE_CASE_					=    self.bottom_root, other.bottom_root
       while i or j:
             if i and ((not j) or i.left_tree_size < j.left_tree_size):
                   combined_roots_list.append((i, True)		)
                   SCREAMING_SNAKE_CASE_					=    i.parent
             else:
                   combined_roots_list.append((j, False)		)
                   SCREAMING_SNAKE_CASE_					=    j.parent
        # Insert links between them
       for i in range(len(_lowerCAmelCase		) - 1		):
             if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
                   SCREAMING_SNAKE_CASE_					=    combined_roots_list[i + 1][0]
                   SCREAMING_SNAKE_CASE_					=    combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
       SCREAMING_SNAKE_CASE_					=    combined_roots_list[0][0]
       while i.parent:
             if (
                 (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
             ) or (
                 i.left_tree_size == i.parent.left_tree_size
                 and i.left_tree_size != i.parent.parent.left_tree_size
             ):
                   # Neighbouring Nodes
                   SCREAMING_SNAKE_CASE_					=    i.left
                   SCREAMING_SNAKE_CASE_					=    i.parent.parent

                   # Merging trees
                   SCREAMING_SNAKE_CASE_					=    i.merge_trees(i.parent		)

                   # Updating links
                   SCREAMING_SNAKE_CASE_					=    previous_node
                   SCREAMING_SNAKE_CASE_					=    next_node
                   if previous_node:
                         SCREAMING_SNAKE_CASE_					=    i
                   if next_node:
                         SCREAMING_SNAKE_CASE_					=    i
             else:
                   SCREAMING_SNAKE_CASE_					=    i.parent
        # Updating self.bottom_root
       while i.left:
             SCREAMING_SNAKE_CASE_					=    i.left
       SCREAMING_SNAKE_CASE_					=    i

       # Update other
       SCREAMING_SNAKE_CASE_					=    self.size
       SCREAMING_SNAKE_CASE_					=    self.bottom_root
       SCREAMING_SNAKE_CASE_					=    self.min_node

       # Return the merged heap
       return self



 def    lowerCAmelCase_						(							self						:	Any       ,       _lowerCAmelCase						:	Dict		):
       if self.size == 0:
             SCREAMING_SNAKE_CASE_					=    Node(_lowerCAmelCase		)
             SCREAMING_SNAKE_CASE_					=    1
             SCREAMING_SNAKE_CASE_					=    self.bottom_root
       else:
             # Create new node
             SCREAMING_SNAKE_CASE_					=    Node(_lowerCAmelCase		)

             # Update size
             self.size += 1

             # update min_node
             if val < self.min_node.val:
                   SCREAMING_SNAKE_CASE_					=    new_node
             # Put new_node as a bottom_root in heap
             SCREAMING_SNAKE_CASE_					=    new_node
             SCREAMING_SNAKE_CASE_					=    self.bottom_root
             SCREAMING_SNAKE_CASE_					=    new_node

             # Consecutively merge roots with same left_tree_size
             while (
                 self.bottom_root.parent
                 and self.bottom_root.left_tree_size
                 == self.bottom_root.parent.left_tree_size
             ):
                   # Next node
                   SCREAMING_SNAKE_CASE_					=    self.bottom_root.parent.parent

                   # Merge
                   SCREAMING_SNAKE_CASE_					=    self.bottom_root.merge_trees(self.bottom_root.parent		)

                   # Update Links
                   SCREAMING_SNAKE_CASE_					=    next_node
                   SCREAMING_SNAKE_CASE_					=    None
                   if next_node:
                         SCREAMING_SNAKE_CASE_					=    self.bottom_root



 def    lowerCAmelCase_						(							self						:	Dict		):
       return self.min_node.val



 def    lowerCAmelCase_						(							self						:	int		):
       return self.size == 0



 def    lowerCAmelCase_						(							self						:	List[Any]		):
       SCREAMING_SNAKE_CASE_					=    self.min_node.val

       # Last element in heap corner case
       if self.size == 1:
             # Update size
             SCREAMING_SNAKE_CASE_					=    0

             # Update bottom root
             SCREAMING_SNAKE_CASE_					=    None

             # Update min_node
             SCREAMING_SNAKE_CASE_					=    None

             return min_value
       # No right subtree corner case
       # The structure of the tree implies that this should be the bottom root
       # and there is at least one other root
       if self.min_node.right is None:
             # Update size
             self.size -= 1

             # Update bottom root
             SCREAMING_SNAKE_CASE_					=    self.bottom_root.parent
             SCREAMING_SNAKE_CASE_					=    None

             # Update min_node
             SCREAMING_SNAKE_CASE_					=    self.bottom_root
             SCREAMING_SNAKE_CASE_					=    self.bottom_root.parent
             while i:
                   if i.val < self.min_node.val:
                         SCREAMING_SNAKE_CASE_					=    i
                   SCREAMING_SNAKE_CASE_					=    i.parent
             return min_value
       # General case
       # Find the BinomialHeap of the right subtree of min_node
       SCREAMING_SNAKE_CASE_					=    self.min_node.right
       SCREAMING_SNAKE_CASE_					=    None
       SCREAMING_SNAKE_CASE_					=    bottom_of_new
       SCREAMING_SNAKE_CASE_					=    1

       # Size, min_node and bottom_root
       while bottom_of_new.left:
             SCREAMING_SNAKE_CASE_					=    size_of_new * 2 + 1
             SCREAMING_SNAKE_CASE_					=    bottom_of_new.left
             if bottom_of_new.val < min_of_new.val:
                   SCREAMING_SNAKE_CASE_					=    bottom_of_new
        # Corner case of single root on top left path
       if (not self.min_node.left) and (not self.min_node.parent):
             SCREAMING_SNAKE_CASE_					=    size_of_new
             SCREAMING_SNAKE_CASE_					=    bottom_of_new
             SCREAMING_SNAKE_CASE_					=    min_of_new
             # print("Single root, multiple nodes case")
             return min_value
       # Remaining cases
       # Construct heap of right subtree
       SCREAMING_SNAKE_CASE_					=    BinomialHeap(
           bottom_root=_lowerCAmelCase       ,       min_node=_lowerCAmelCase       ,       heap_size=_lowerCAmelCase		)

       # Update size
       SCREAMING_SNAKE_CASE_					=    self.size - 1 - size_of_new

       # Neighbour nodes
       SCREAMING_SNAKE_CASE_					=    self.min_node.left
       SCREAMING_SNAKE_CASE_					=    self.min_node.parent

       # Initialize new bottom_root and min_node
       SCREAMING_SNAKE_CASE_					=    previous_node or next_node
       SCREAMING_SNAKE_CASE_					=    next_node

       # Update links of previous_node and search below for new min_node and
       # bottom_root
       if previous_node:
             SCREAMING_SNAKE_CASE_					=    next_node

             # Update bottom_root and search for min_node below
             SCREAMING_SNAKE_CASE_					=    previous_node
             SCREAMING_SNAKE_CASE_					=    previous_node
             while self.bottom_root.left:
                   SCREAMING_SNAKE_CASE_					=    self.bottom_root.left
                   if self.bottom_root.val < self.min_node.val:
                         SCREAMING_SNAKE_CASE_					=    self.bottom_root
       if next_node:
             SCREAMING_SNAKE_CASE_					=    previous_node

             # Search for new min_node above min_node
             SCREAMING_SNAKE_CASE_					=    next_node
             while i:
                   if i.val < self.min_node.val:
                         SCREAMING_SNAKE_CASE_					=    i
                   SCREAMING_SNAKE_CASE_					=    i.parent
        # Merge heaps
       self.merge_heaps(_lowerCAmelCase		)

       return min_value



 def    lowerCAmelCase_						(							self						:	Optional[int]		):
       SCREAMING_SNAKE_CASE_					=    self.bottom_root
       while top_root.parent:
             SCREAMING_SNAKE_CASE_					=    top_root.parent
       # preorder
       SCREAMING_SNAKE_CASE_					=    []
       self.__traversal(_lowerCAmelCase       ,       _lowerCAmelCase		)
       return heap_pre_order



 def    lowerCAmelCase_						(							self						:	Dict       ,       _lowerCAmelCase						:	Tuple       ,       _lowerCAmelCase						:	Dict       ,       _lowerCAmelCase						:	List[str]=0		):
       if curr_node:
             preorder.append((curr_node.val, level)		)
             self.__traversal(curr_node.left       ,       _lowerCAmelCase       ,       level + 1		)
             self.__traversal(curr_node.right       ,       _lowerCAmelCase       ,       level + 1		)
       else:
             preorder.append(('#', level)		)




 def __str__(							self						:	List[Any]		):
       if self.is_empty():
             return ""
       SCREAMING_SNAKE_CASE_					=    self.pre_order()

       return "\n".join(('-' * level + str(_lowerCAmelCase		)) for value, level in preorder_heap		)


# Unit Tests
if __name__ == "__main__":
      import doctest

      doctest.testmod()





from __future__ import annotations

def       UpperCAmelCase_							(   __UpperCAmelCase		:			list[int]							)      ->				list[int]:
      SCREAMING_SNAKE_CASE_					=    [0] * len(__UpperCAmelCase							)
      for i in range(1    ,    len(__UpperCAmelCase							)							):
            SCREAMING_SNAKE_CASE_					=    duration_times[i - 1] + waiting_times[i - 1]
      return waiting_times

def       UpperCAmelCase_							(   __UpperCAmelCase		:			list[int]    ,    __UpperCAmelCase		:			list[int]							)      ->				list[int]:
      return [
          duration_time + waiting_times[i]
          for i, duration_time in enumerate(__UpperCAmelCase							)
      ]

def       UpperCAmelCase_							(   __UpperCAmelCase		:			list[int]							)      ->				float:
      return sum(__UpperCAmelCase							) / len(__UpperCAmelCase							)

def       UpperCAmelCase_							(   __UpperCAmelCase		:			list[int]							)      ->				float:
      return sum(__UpperCAmelCase							) / len(__UpperCAmelCase							)


if __name__ == "__main__":
   # process id's
   lowerCamelCase__				:     Union[str, Any]			       =							[1, 2, 3]

   # ensure that we actually have processes
   if len(processes) == 0:
      print('Zero amount of processes')
      raise SystemExit(0)

   # duration time of all processes
   lowerCamelCase__				:     Optional[Any]			       =							[19, 8, 9]

   # ensure we can match each id to a duration time
   if len(duration_times) != len(processes):
      print('Unable to match all id\'s with their duration time')
      raise SystemExit(0)

   # get the waiting times and the turnaround times
   lowerCamelCase__				:     Dict			       =							calculate_waiting_times(duration_times)
   lowerCamelCase__				:     int			       =							calculate_turnaround_times(duration_times, waiting_times)

   # get the average times
   lowerCamelCase__				:     Any			       =							calculate_average_waiting_time(waiting_times)
   lowerCamelCase__				:     Tuple			       =							calculate_average_turnaround_time(turnaround_times)

   # print all the results
   print('Process ID\tDuration Time\tWaiting Time\tTurnaround Time')
   for i, process in enumerate(processes):
      print(
          f'''{process}\t\t{duration_times[i]}\t\t{waiting_times[i]}\t\t'''
          f'''{turnaround_times[i]}'''
      )
   print(f'''Average waiting time = {average_waiting_time}''')
   print(f'''Average turn around time = {average_turnaround_time}''')