class MinHeap :

	# Time O(1) Space O(1)
	def __init__(self, capacity) :
		self.maxSize = capacity
		self.length = 0
		self.heap = [None]*capacity 
    
	# Insert a new value, Time O(h), Space O(1), n is number of items in heap
	# h is height of heap (complete binary tree) h = log(n)
	def insert(self, value):
		if self.length >= self.maxSize :
			print("heap reach max size, return")
			return
		self.heap[self.length] = value	# start from last		
		self.heapUp(self.length)

	# Time O(h), Space O(1)	
	def	heapUp(self, pos) :
		parentPos = int((pos-1)/2)
		value = self.heap[pos]
		while pos > 0 and  value < self.heap[parentPos] :
			self.heap[pos] = self.heap[parentPos]
			pos = parentPos 
			parentPos= int((parentPos-1)/2)		
		self.heap[pos] = value; 
		self.length += 1
    	 
    # Remove from min (first one), Time O(h), Space O(1)
	def remove(self) :
		if self.length == 0: 
			print("heap is empty")
			return None		
		max = self.heap[0]
		self.heap[0] = self.heap[self.length-1] # put the last at first
		self.length -= 1
		self.heapDown(0)
		return max
    
    # Time O(h), Space O(1)
	def heapDown(self, pos) :
		item = self.heap[pos]
		index = 0
		while pos < int(self.length/2) :
			left = 2*pos + 1
			right = 2*pos + 2
			if right < self.length and self.heap[left] > self.heap[right]:
				index = right
			else:
				index = left
			if item <= self.heap[index]:
				break
			self.heap[pos] = self.heap[index]
			pos = index		
		self.heap[pos] = item;   
      
    #Time O(n), Space O(1), n is number of items in heap
	def search(self, key) :
		for i in range(0, self.length) :
			if key == self.heap[i]:
				return True
		return False
    
    # Traverse as array, it is also level order of tree, Time O(n), Space O(n)
	def levelOrder(self) :
		s = []
		for i in range(0, self.length):
			s.append(self.heap[i]) 		
		return s
     
	# Traverse as tree preorder, Time O(n), Space (n)
	def preorder(self) :		
		output = []
		self.preorderRec(0, output)
		return output
	
	# Recursion helper, Time O(n), Space (h)
	def preorderRec(self, nodeIndex, output) :	
		if nodeIndex > self.length-1 :
			return
		output.append(self.heap[nodeIndex])
		self.preorderRec( 2*nodeIndex + 1, output)									
		self.preorderRec( 2*nodeIndex + 2, output) 

	# Traverse as tree inorder, Time O(n), Space (n)
	def inorder(self) :		
		output = []
		self.inorderRec(0, output)
		return output
	
	# Recursion helper, Time O(n), Space (h)
	def inorderRec(self, nodeIndex, output) :
		if nodeIndex > self.length-1 :
			return	
		self.inorderRec(2* nodeIndex +1, output)					
		output.append(self.heap[nodeIndex])  
		self.inorderRec(2*nodeIndex + 2, output) 	
	
	# Traverse as tree postorder, Time O(n), Space O(n)
	def postorder(self) :		
		output = []
		self.postorderRec(0, output)
		return output

	# Recursion helper, Time O(n), Space (h)
	def postorderRec(self, nodeIndex, output) :
		if (nodeIndex > self.length-1):
			return
		self.postorderRec(2*nodeIndex + 1, output)								
		self.postorderRec(2*nodeIndex + 2, output) 	
		output.append(self.heap[nodeIndex]) 
	
minHeap = MinHeap(10)  #capacity 10
minHeap.insert(5)          
minHeap.insert(4)
minHeap.insert(8)
minHeap.insert(2)
minHeap.insert(7)
minHeap.insert(9)
minHeap.insert(2)
minHeap.insert(10)
minHeap.insert(6)    
print("size: " + str(minHeap.length))
print("level order: ")
print(minHeap.levelOrder())
print("preorder: ")
print(minHeap.preorder())
print("inorder: ")
print(minHeap.inorder())
print("postorder: ")
print(minHeap.postorder())

#search
key = 3
print("has " + str(key) +": " + str(minHeap.search(key)))
key =7
print("has " + str(key) +": " + str(minHeap.search(key)))

# remove the min value in heap
print("\nRemove the min val: " + str(minHeap.remove()))     
print("size: " + str(minHeap.length))
print("level order: ")
print(minHeap.levelOrder())
print("preorder: ")
print(minHeap.preorder())
print("inorder: ")
print(minHeap.inorder())
print("postorder: ")
print(minHeap.postorder())