max_binary_heap.py

max_binary_heap.py

class MaxBinaryHeap:
	def __init__(self, values=[]):
		self.values = values
		self.build_max_heap()
	
	def max(self):
		"""return first element in the array"""
		if len(self.values) > 0:
			return self.value[0]
		else:
			return None
	
	def heap_size(self):
		return len(self.values)
	
	def build_max_heap(self):
		for i in range(self.heap_size() // 2, 0, -1):
			self.max_heapify(i)
		
	def max_heapify(self, i):
		l = self.left(i)
		r = self.right(i)
		
		if l < self.heap_size() and self.values[l] > self.values[i]:
			largest = l
		else:
			largest = i
		
		if r < self.heap_size() and self.values[r] > self.values[largest]:
			largest = r
		
		if largest != i:
			self.values[i], self.values[largest] = self.values[largest], self.values[i]
			self.max_heapify(largest)
		
	def parent(self, node_index):
		"""returns index of node's parent"""
		return node_index // 2
	
	def left(self, node_index):
		"""returns index of node's left child"""
		return node_index * 2	
	
	def right(self, node_index):
		"""returns index of node's right child"""
		return 2 * node_index + 1
	
	def print_as_list(self):
		"""print heap in list form"""
		print(self.values)	
		
	def print_as_tree(self, index = 1, indent = 0):
		"""
		print heap in tree form
		for example: 
		input: [16, 14, 9, 10, 8, 1, 4, 2, 3, 7]
		output:
		16
			14
				10
					2
					3
				8
					7
			9
				1
				4
		"""
		if index > len(self.values):
			return None
		else:
			print('  ' * indent + str(self.values[index-1]))
			self.print_as_tree(self.left(index), indent + 1)
			self.print_as_tree(self.right(index), indent + 1)
		
heap = MaxBinaryHeap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7])
heap.print_as_list()
heap.print_as_tree()