Python Algorithm Pt.8: heap tree

Yay! Its Python Algorithm time…again! I have no idea why I am celebrating!

Alright. What is heap tree? It is a type of…lets say…sort. It is quite similar to binary tree. The heap tree is quite an important knowledge in python. I will now post an example:

class Heaptree():
def __init__(self):
self.heap = []
self.size = 0
def data_down (self,i):
while (i * 2 + 2) <= self.size:
mi = self.get_min_index(i)
if self.heap[i] > self.heap[mi]:
self.heap[i], self.heap[mi] = self.heap[mi], self.heap[i]
i = mi
def get_min_index(self,i):
if i *2 + 2 >= self.size:
return i * 2 + 1
else:
if self.heap[i*2+1] < self.heap[i*2+2]:
return i * 2 + 1
else:
return i * 2 + 2
def build_heap(self, mylist):
i = (len(mylist) // 2) - 1
self.size = len(mylist)
self.heap = mylist
while (i >= 0):
self.data_down(i)
i = i - 1
h = [10, 21, 5, 9, 13, 28, 3]
print("Before run   = ", h)
obj = Heaptree()
obj.build_heap(h)
print("After run = ", obj.heap)

Here is what it *should* look like:

Result

As you can see running the heap tree requires effort and time. It is quite difficult, and I dont really understand it well. What it is supposed to do is to sort the numbers to the right order by rearranging them, putting the smallest number on reserve…and so on. By having the current smallest put on the result, we can have a definitive order of the numbers, from smallest to largest. See my post on binary tree to see some rules for yourself. One important note is that the switchin of numbers also have to be done.