# The largest is at root
class MaxHeap:
	#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(logn), Space O(1), n is number of items in heap
	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)
		self.length += 1 

	#Time O(logn), 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 

    #Remove from max (first one), Time O(logn), 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 last at first
		self.length -= 1 
		self.heapDown(0)
		return max
    
    # Time O(logn), 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 O(n)
	def preorder(self):		
		output = []
		self.preorderRec(0, output)
		return output
	
	# Recursion helper, Time O(n), Space O(n)
	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 O(n)
	def inorder(self):		
		output = []
		self.inorderRec(0, output)
		return output
	
	# Recursion helper, Time O(n), Space O(n)
	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 O(n)
	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]) 

if __name__ == "__main__":
	maxHeap = MaxHeap(10)  #capacity 10
	maxHeap.insert(5)          
	maxHeap.insert(4)
	maxHeap.insert(8)
	maxHeap.insert(2)
	maxHeap.insert(7)
	maxHeap.insert(9)
	maxHeap.insert(2)
	maxHeap.insert(10)
	maxHeap.insert(6)    
	print("size: " + str(maxHeap.length))
	print("level order: ")
	print(maxHeap.levelOrder())
	print("preorder: ")
	print(maxHeap.preorder())
	print("inorder: ")
	print(maxHeap.inorder())
	print("postorder: ")
	print(maxHeap.postorder())

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

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