


"""simple docstring"""






class       lowerCamelCase_		:





				"""simple docstring"""







				def __init__(    self  ):
								SCREAMING_SNAKE_CASE__  				=					[0]
								SCREAMING_SNAKE_CASE__  				=					0



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								SCREAMING_SNAKE_CASE__  				=					self.__heap[i]
								while i // 2 > 0:
												if self.__heap[i] > self.__heap[i // 2]:
																SCREAMING_SNAKE_CASE__  				=					self.__heap[i // 2]
																SCREAMING_SNAKE_CASE__  				=					temporary
												i //= 2



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								self.__heap.append(UpperCAmelCase__  )
								self.__size += 1
								self.__swap_up(self.__size  )



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								while self.__size >= 2 * i:
												if 2 * i + 1 > self.__size:
																SCREAMING_SNAKE_CASE__  				=					2 * i
												else:
																if self.__heap[2 * i] > self.__heap[2 * i + 1]:
																				SCREAMING_SNAKE_CASE__  				=					2 * i
																else:
																				SCREAMING_SNAKE_CASE__  				=					2 * i + 1
												SCREAMING_SNAKE_CASE__  				=					self.__heap[i]
												if self.__heap[i] < self.__heap[bigger_child]:
																SCREAMING_SNAKE_CASE__  				=					self.__heap[bigger_child]
																SCREAMING_SNAKE_CASE__  				=					temporary
												SCREAMING_SNAKE_CASE__  				=					bigger_child



				def 	lowerCAmelCase__		(    self  ):
								SCREAMING_SNAKE_CASE__  				=					self.__heap[1]
								SCREAMING_SNAKE_CASE__  				=					self.__heap[self.__size]
								self.__size -= 1
								self.__heap.pop()
								self.__swap_down(1  )
								return max_value



				@property
				def 	lowerCAmelCase__		(    self  ):
								return self.__heap[1:]






				def __len__(    self  ):
								return self.__size


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	# create an instance of BinaryHeap
	_lowerCamelCase  =	BinaryHeap()
	binary_heap.insert(6)
	binary_heap.insert(10)
	binary_heap.insert(15)
	binary_heap.insert(12)
	# pop root(max-values because it is max heap)
	print(binary_heap.pop())  # 15
	print(binary_heap.pop())  # 12
	# get the list and size after operations
	print(binary_heap.get_list)
	print(len(binary_heap))




"""simple docstring"""






class       lowerCamelCase_		:





				"""simple docstring"""







				class       lowerCamelCase_		:





								"""simple docstring"""







								_lowerCAmelCase   :   Dict   				=       "_prev", "_data", "_next"



								def __init__(    self							,		UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  ):
												SCREAMING_SNAKE_CASE__  				=					link_p
												SCREAMING_SNAKE_CASE__  				=					element
												SCREAMING_SNAKE_CASE__  				=					link_n






								def 	lowerCAmelCase__		(    self  ):
												return (
												    f''' Prev -> {self._prev is not None}, Next -> {self._next is not None}'''
												)



				def __init__(    self  ):
								SCREAMING_SNAKE_CASE__  				=					self._Node(UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  )
								SCREAMING_SNAKE_CASE__  				=					self._Node(UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  )
								SCREAMING_SNAKE_CASE__  				=					self._trailer
								SCREAMING_SNAKE_CASE__  				=					self._header
								SCREAMING_SNAKE_CASE__  				=					0



				def __len__(    self  ):
								return self._size



				def 	lowerCAmelCase__		(    self  ):
								return self.__len__() == 0



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  ):
								# Create new_node by setting it's prev.link -> header
								# setting it's next.link -> trailer
								SCREAMING_SNAKE_CASE__  				=					self._Node(UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  )
								SCREAMING_SNAKE_CASE__  				=					new_node
								SCREAMING_SNAKE_CASE__  				=					new_node
								self._size += 1
								return self






				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								SCREAMING_SNAKE_CASE__  				=					node._prev
								SCREAMING_SNAKE_CASE__  				=					node._next

								SCREAMING_SNAKE_CASE__  				=					successor
								SCREAMING_SNAKE_CASE__  				=					predecessor
								self._size -= 1
								SCREAMING_SNAKE_CASE__  				=					node._data
								SCREAMING_SNAKE_CASE__  				=					SCREAMING_SNAKE_CASE__  				=					SCREAMING_SNAKE_CASE__  				=					None
								del node
								return temp


class       lowerCamelCase_		(      _DoublyLinkedBase ):





				"""simple docstring"""







				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise Exception("List is empty"  )
								return self._header._next._data



				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise Exception("List is empty"  )
								return self._trailer._prev._data



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								return self._insert(self._header							,		UpperCAmelCase__							,		self._header._next  )



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								return self._insert(self._trailer._prev							,		UpperCAmelCase__							,		self._trailer  )



				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise IndexError("remove_first from empty list"  )
								return self._delete(self._header._next  )






				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise IndexError("remove_first from empty list"  )
								return self._delete(self._trailer._prev  )
