binary heap class

ns_Heap.py

 a min heap implementation for use with micropython





class ns_Heap(object):
	""""
	Attributes:
		heap: List representation of a min heap
	Implementation Notes:
		The heap is implemented as a list.  The algorithm uses list indexes
        counting from 1 to n.  Where the size of the heap is n.  The list
		has a null data values at the normal list position of 0.  The heap is 
        sorted so that the root containing the max value is position 1.  The numbering
        continues so that left is at postion 2 and right is at position 3. Likewise
        the left and right of node 2 is 4 and 5.  Hence left = 2i and right is 2*i + 1.
        This relationship is why list position 0 is not used.
	"""
	def __init__(self, heap=None):
		# the algo book uses indexes which start at 1 instead of 0
		# add a dummy value at the first item
		self.heap_list = [-3367]
		if heap is None:
			return

		# append the list parameter after the dummy value	
		self.heap_list.extend(heap)

		# we will not use len() of the list but instead use size
		self.heap_size = len(self.heap_list) - 1

		# Go ahead do make sure max heap property is applied
		self.build_max_heap()
		
		#self.heap_list = [] if heap is None else heap

	# Used to print/dump the heap as a list
	def __repr__(self):
		return 'ns_Heap({!r})'.format(self.heap_list[1:])

	def size(self):
		return self.heap_size

	def parent(self, i):
		if i < 1:
			assert 0, "heap_index_min"
		if i > self.heap_size:
			assert 0, "heap_index_max"

		return i // 2

	def left(self, i):
		if i < 1:
			assert 0, "heap_index_min"
		if i > self.heap_size:
			assert 0, "heap_index_max"

		return 2 * i

	def right(self, i):
		if i < 1:
			assert 0, "heap_index_min"
		if i > self.heap_size:
			assert 0, "heap_index_max"

		return 2 * i + 1

	def max_heapify(self,i):
		if i < 1:
			assert 0, "heap_index_min"
		if i > self.heap_size:
			assert 0, "heap_index_max"

		left = self.left(i)
		right = self.right(i)

		if left <= self.heap_size and self.heap_list[left] > self.heap_list[i]:
			largest = left
		else:
			largest = i

	
		if right <= self.heap_size and self.heap_list[right] > self.heap_list[largest]:
			largest = right

		if largest != i:
			# swap heap_list[i] with heap_list[largest]
			temp_value = self.heap_list[i]
			self.heap_list[i] = self.heap_list[largest]
			self.heap_list[largest] = temp_value
			self.max_heapify(largest)

	def build_max_heap(self):
		
		for i in range(self.heap_size//2, 0, -1):	# can also wrap with reversed()
			self.max_heapify(i)

	def peek_max(self):
		if self.heap_size < 1:
			assert 0, "heap_empty"

		return self.heap_list[1]

	def extract_max(self):
		if self.heap_size < 1:
			assert 0, "heap_underflow"

		the_max = self.heap_list[1]
		self.heap_list[1] = self.heap_list.pop()
		self.heap_size = len(self.heap_list) - 1
		self.max_heapify(1)
		return the_max

test_heap.py

from ns_Heap import ns_Heap

#print("Init heap with [1,3,5]")

# a heap already setup with max heap property built in
x = ns_Heap([16,14,10,8,7,9,3,2,4,1])
# a list which is not setup with max heap property
#x = ns_Heap([1,2,3,4,7,8,9,10,14,16])
#x = ns_Heap([5,3,1])


print("x is %s" % (x))
print("size of x is %s" % (x.size()))

print("do parent for each node from 2 to 0 index")
print(x.parent(2))
print(x.parent(1))
#print(x.parent(0))


print("do left for each node from 2 to 0 index")
print(x.left(2))
print(x.left(1))
#print(x.left(0))


print("do right for each node from 2 to 0 index")
print(x.right(2))
print(x.right(1))
#print(x.right(0))

print("max_heapify")
#x.max_heapify(1)
x.build_max_heap()
print("x is %s" % (x))


#print("Add some even values: 6")

#x.add(6)

#print("x is %s" % (x))


#print("Add some even values: 0")

#x.add(0)

#print("x is %s" % (x))

#print("Add some even values: 2")

#x.add(2)

#print("x is %s" % (x))

#x.peak_max()
print("max is %d" % ( x.peak_max() ) )
print("extrat_max returns %d" % ( x.extract_max() ) )
print("x is %s" % (x))