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 = 0def 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 = midef get_min_index(self,i):if i *2 + 2 >= self.size:return i * 2 + 1else:if self.heap[i*2+1] < self.heap[i*2+2]:return i * 2 + 1else:return i * 2 + 2def build_heap(self, mylist):i = (len(mylist) // 2) - 1self.size = len(mylist)self.heap = mylistwhile (i >= 0):self.data_down(i)i = i - 1h = [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:
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.