
class      _lowerCAmelCase :




				def __init__( self    ,    _UpperCamelCase					)    ->				List[str]:
							lowerCAmelCase_      =     val
							# Number of nodes in left subtree
							lowerCAmelCase_      =     0
							lowerCAmelCase_      =     None
							lowerCAmelCase_      =     None
							lowerCAmelCase_      =     None




				def 					__a						( self    ,    _UpperCamelCase					)    ->				Dict:
							assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

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





class      _lowerCAmelCase :




				def __init__( self    ,    _UpperCamelCase=None    ,    _UpperCamelCase=None    ,    _UpperCamelCase=0					)    ->				str:
							lowerCAmelCase_      =     heap_size
							lowerCAmelCase_      =     bottom_root
							lowerCAmelCase_      =     min_node




				def 					__a						( self    ,    _UpperCamelCase					)    ->				Optional[Any]:

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

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

							# Order roots by left_subtree_size
							lowerCAmelCase_      =     []
							lowerCAmelCase_     ,  lowerCAmelCase_      =     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)					)
													lowerCAmelCase_      =     i.parent
										else:
													combined_roots_list.append((j, False)					)
													lowerCAmelCase_      =     j.parent
        # Insert links between them
							for i in range(len(_UpperCamelCase					) - 1					):
										if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
													lowerCAmelCase_      =     combined_roots_list[i + 1][0]
													lowerCAmelCase_      =     combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
							lowerCAmelCase_      =     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
													lowerCAmelCase_      =     i.left
													lowerCAmelCase_      =     i.parent.parent

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

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

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

							# Return the merged heap
							return self




				def 					__a						( self    ,    _UpperCamelCase					)    ->				str:
							if self.size == 0:
										lowerCAmelCase_      =     Node(_UpperCamelCase					)
										lowerCAmelCase_      =     1
										lowerCAmelCase_      =     self.bottom_root
							else:
										# Create new node
										lowerCAmelCase_      =     Node(_UpperCamelCase					)

										# Update size
										self.size += 1

										# update min_node
										if val < self.min_node.val:
													lowerCAmelCase_      =     new_node
										# Put new_node as a bottom_root in heap
										lowerCAmelCase_      =     new_node
										lowerCAmelCase_      =     self.bottom_root
										lowerCAmelCase_      =     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
													lowerCAmelCase_      =     self.bottom_root.parent.parent

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

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




				def 					__a						( self					)    ->				int:
							return self.min_node.val




				def 					__a						( self					)    ->				Dict:
							return self.size == 0




				def 					__a						( self					)    ->				Optional[Any]:
							lowerCAmelCase_      =     self.min_node.val

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

										# Update bottom root
										lowerCAmelCase_      =     None

										# Update min_node
										lowerCAmelCase_      =     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
										lowerCAmelCase_      =     self.bottom_root.parent
										lowerCAmelCase_      =     None

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

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

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

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

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

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

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

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

							return min_value




				def 					__a						( self					)    ->				List[Any]:
							lowerCAmelCase_      =     self.bottom_root
							while top_root.parent:
										lowerCAmelCase_      =     top_root.parent
							# preorder
							lowerCAmelCase_      =     []
							self.__traversal(_UpperCamelCase    ,    _UpperCamelCase					)
							return heap_pre_order




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase=0					)    ->				Any:
							if curr_node:
										preorder.append((curr_node.val, level)					)
										self.__traversal(curr_node.left    ,    _UpperCamelCase    ,    level + 1					)
										self.__traversal(curr_node.right    ,    _UpperCamelCase    ,    level + 1					)
							else:
										preorder.append(("#", level)					)




				def __str__( self					)    ->				Any:
							if self.is_empty():
										return ""
							lowerCAmelCase_      =     self.pre_order()

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


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

			doctest.testmod()





# This Python program implements an optimal binary search tree (abbreviated BST)
# building dynamic programming algorithm that delivers O(n^2) performance.
#
# The goal of the optimal BST problem is to build a low-cost BST for a
# given set of nodes, each with its own key and frequency. The frequency
# of the node is defined as how many time the node is being searched.
# The search cost of binary search tree is given by this formula:
#
# cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
#
# where n is number of nodes in the BST. The characteristic of low-cost
# BSTs is having a faster overall search time than other implementations.
# The reason for their fast search time is that the nodes with high
# frequencies will be placed near the root of the tree while the nodes
# with low frequencies will be placed near the leaves of the tree thus
# reducing search time in the most frequent instances.
import sys
from random import randint





class      _lowerCAmelCase :




				def __init__( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				str:
							lowerCAmelCase_      =     key
							lowerCAmelCase_      =     freq




				def __str__( self					)    ->				Any:
							return f"""Node(key={self.key}, freq={self.freq})"""






def        lowerCamelCase__    (    __lowerCAmelCase  :  Optional[int]   ,							__lowerCAmelCase  :  Dict   ,							__lowerCAmelCase  :  Optional[Any]   ,							__lowerCAmelCase  :  Optional[int]   ,							__lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  List[Any]    ):




			"""simple docstring"""


			if i > j or i < 0 or j > len(__lowerCAmelCase    ) - 1:
						return

			lowerCAmelCase_      =     root[i][j]
			if parent == -1:  # root does not have a parent
						print(F"""{key[node]} is the root of the binary search tree."""    )
			elif is_left:
						print(F"""{key[node]} is the left child of key {parent}."""    )
			else:
						print(F"""{key[node]} is the right child of key {parent}."""    )

			print_binary_search_tree(__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							node - 1   ,							key[node]   ,							__lowerCAmelCase    )
			print_binary_search_tree(__lowerCAmelCase   ,							__lowerCAmelCase   ,							node + 1   ,							__lowerCAmelCase   ,							key[node]   ,							__lowerCAmelCase    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  Union[str, Any]    ):




			"""simple docstring"""


			nodes.sort(key=lambda __lowerCAmelCase    : node.key    )

			lowerCAmelCase_      =     len(__lowerCAmelCase    )

			lowerCAmelCase_      =     [nodes[i].key for i in range(__lowerCAmelCase    )]
			lowerCAmelCase_      =     [nodes[i].freq for i in range(__lowerCAmelCase    )]

			# This 2D array stores the overall tree cost (which's as minimized as possible);
			# for a single key, cost is equal to frequency of the key.
			lowerCAmelCase_      =     [[freqs[i] if i == j else 0 for j in range(__lowerCAmelCase    )] for i in range(__lowerCAmelCase    )]
			# sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
			# array
			lowerCAmelCase_      =     [[freqs[i] if i == j else 0 for j in range(__lowerCAmelCase    )] for i in range(__lowerCAmelCase    )]
			# stores tree roots that will be used later for constructing binary search tree
			lowerCAmelCase_      =     [[i if i == j else 0 for j in range(__lowerCAmelCase    )] for i in range(__lowerCAmelCase    )]

			for interval_length in range(2   ,							n + 1    ):
						for i in range(n - interval_length + 1    ):
									lowerCAmelCase_      =     i + interval_length - 1

									lowerCAmelCase_      =     sys.maxsize  # set the value to "infinity"
									lowerCAmelCase_      =     total[i][j - 1] + freqs[j]

									# Apply Knuth's optimization
									# Loop without optimization: for r in range(i, j + 1):
									for r in range(root[i][j - 1]   ,							root[i + 1][j] + 1    ):  # r is a temporal root
												lowerCAmelCase_      =     dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
												lowerCAmelCase_      =     dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
												lowerCAmelCase_      =     left + total[i][j] + right

												if dp[i][j] > cost:
															lowerCAmelCase_      =     cost
															lowerCAmelCase_      =     r

			print("Binary search tree nodes:"    )
			for node in nodes:
						print(__lowerCAmelCase    )

			print(F"""\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}."""    )
			print_binary_search_tree(__lowerCAmelCase   ,							__lowerCAmelCase   ,							0   ,							n - 1   ,							-1   ,							__lowerCAmelCase    )






def        lowerCamelCase__    (    ):




			"""simple docstring"""


			lowerCAmelCase_      =     [Node(__lowerCAmelCase   ,							randint(1   ,							50    )    ) for i in range(10   ,							0   ,							-1    )]
			find_optimal_binary_search_tree(__lowerCAmelCase    )


if __name__ == "__main__":
			main()



