Heap
class Heap:
def __init__(self):
self.lst = []
def get_left_child_index(self, index):
return (2 * index) + 1
def get_right_child_index(self, index):
return (2 * index) + 2
def get_parent_index(self, index):
return (index - 1) // 2
def has_left_child(self, index):
return self.get_left_child_index(index) < len(self.lst)
def has_right_child(self, index):
return self.get_right_child_index(index) < len(self.lst)
def has_parent(self, index):
return self.get_parent_index(index) >= 0
def swap(self, first, second):
self.lst[first], self.lst[second] = self.lst[second], self.lst[first]
def peek(self):
if not self.lst:
return None
return self.lst[0]
def poll(self):
if not self.lst:
return None
item = self.lst[0]
self.swap(0, -1)
self.lst.pop()
self.heapify_down()
return item
def add(self, data):
self.lst.append(data)
self.heapify_up()
def heapify_up(self):
index = len(self.lst) - 1
while self.has_parent(index):
parent_index = self.get_parent_index(index)
if self.lst[parent_index] > self.lst[index]:
self.swap(parent_index, index)
index = parent_index
def heapify_down(self):
index = 0
while self.has_left_child(index):
smaller_index = self.get_left_child_index(index)
if self.has_right_child(index) and self.lst[self.get_right_child_index(index)] < self.lst[smaller_index]:
smaller_index = self.get_right_child_index(index)
if self.lst[index] < self.lst[smaller_index]:
break
self.swap(index, smaller_index)
index = smaller_index
h = Heap()
h.add(20)
h.add(17)
h.add(15)
h.add(10)
print(h.poll())
print(h.poll())
print(h.poll())
print(h.poll())
Last updated