# Min Heap Tree Implementation in python 3

I wrote a min-heap using a binary tree. How can I improve the time complexity of insert and delete function to be $$\\mathcal{O}(log(n))\$$?

'''
Min Heap Tree Implementation
'''

class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

class HeapBT:
def __init__(self):

def insert(self, data):
return

lst = []
while lst:
currentNode = lst.pop(0)
if currentNode.left is None:
currentNode.left = Node(data)
break

if currentNode.right is None:
currentNode.right = Node(data)
break

if currentNode.left is not None:
lst.append(currentNode.left)

if currentNode.right is not None:
lst.append(currentNode.right)

self.heapifyBottomUp(data)

def bfs(self):
return
lst = []

while lst:
currentNode = lst.pop(0)
print(currentNode.data)

if currentNode.left is not None:
lst.append(currentNode.left)

if currentNode.right is not None:
lst.append(currentNode.right)

def heapifyBottomUp(self, data):
count = 1
while count:
count = 0
lst = []
while lst:
currentNode = lst.pop(0)
if currentNode.left is not None:
if currentNode.left.data == data:
if currentNode.data > currentNode.left.data:
count = 1
temp = currentNode.data
currentNode.data = currentNode.left.data
currentNode.left.data = temp
break

elif currentNode.left != data:
lst.append(currentNode.left)

if currentNode.right is not None:
if currentNode.right.data == data:
if currentNode.data > currentNode.right.data:
count = 1
temp = currentNode.data
currentNode.data = currentNode.right.data
currentNode.right.data = temp
break

elif currentNode.right != data:
lst.append(currentNode.right)

def heapifyTopDown(self, node):
if node is None:
return

if node.left is not None and node.right is not None:
if node.left.data < node.data and node.right.data < node.data:
if node.left.data < node.right.data:
temp = node.data
node.data = node.left.data
node.left.data = temp
self.heapifyTopDown(node.left)
return

else:
temp = node.data
node.data = node.right.data
node.right.data = temp
self.heapifyTopDown(node.right)
return

elif node.left.data < node.data and node.right.data > node.data:
temp = node.left.data
node.left.data = node.data
node.data = temp
self.heapifyTopDown(node.left)
return

else:
temp = node.right.data
node.right.data = node.data
node.data = temp
self.heapifyTopDown(node.right)
return

elif node.left is not None:
if node.left.data < node.data:
temp = node.data
node.data = node.left.data
node.left.data = temp
self.heapifyTopDown(node.left)
return

elif node.right is not None:
if node.right.data < node.data:
temp = node.data
node.data = node.right.data
node.right.data = node.data
self.heapifyTopDown(node.right)
return

def pop(self):
return 'Heap is empty.'
return data
lst = []
while lst:
currentNode = lst.pop(0)

if currentNode.left is not None:
lst.append(currentNode.left)

if currentNode.right is not None:
lst.append(currentNode.right)

leafData = currentNode.data

lst = []
while lst:
currentNode = lst.pop(0)

if currentNode.left is not None:
if currentNode.left.data == leafData:
currentNode.left = None
break
else:
lst.append(currentNode.left)

if currentNode.right is not None:
if currentNode.right.data == leafData:
currentNode.right = None
break
else:
lst.append(currentNode.right)

return data

def peek(self):

avl = HeapBT()

avl.insert(11)
avl.insert(10)
avl.insert(9)
avl.insert(8)
avl.insert(7)
avl.insert(6)
avl.insert(5)
avl.insert(4)
avl.insert(3)
avl.insert(2)
avl.insert(1)
avl.insert(-1)
avl.insert(43)
avl.insert(34)
avl.insert(53)
avl.insert(-1123)
avl.insert(-100)
avl.insert(-11233)

#avl.bfs()
print
print
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.peek(),'peek')
print

avl.bfs()

• Is there a reason why you implement binary heap using a binary tree? It is much simpler to use a list to implement binary heap, with log performance on insert and delete. Oct 17, 2019 at 14:48

To achieve the $$\\mathcal{O}(log(n))\$$ time complexity of insert and delete functions you should store the binary tree as an array - Heap implementation. Because you need to have a link to the last element for performing insert and delete operations and the easiest (common) way to track this link is an array representation of the binary tree. You can devise your own method of tracking the last element for your binary tree representation, but I think it will be similar to the array method at the end.

My implementation:

class BinHeap:
def __init__(self):
self.lst = []

def insert(self, data):
self.lst.append(data)
self.heapify_up(len(self.lst) - 1)

def pop_root(self):
root = self.lst[0]
last = self.lst.pop()

if len(self.lst) > 0:
self.lst[0] = last
self.heapify_down(0, 0)

return root

def heapify_down(self, parent_idx, child_idx):
if child_idx >= len(self.lst):
return

parent_greater_bool = self.lst[parent_idx] > self.lst[child_idx]

if parent_greater_bool:
self.lst[parent_idx], self.lst[child_idx] = self.lst[child_idx], self.lst[parent_idx]

if parent_greater_bool or parent_idx == 0:
self.heapify_down(child_idx, child_idx * 2 + 1)
self.heapify_down(child_idx, child_idx * 2 + 2)

def heapify_up(self, child_idx):
parent_idx = (child_idx - 1) // 2

if parent_idx < 0:
return

if self.lst[parent_idx] > self.lst[child_idx]:
self.lst[parent_idx], self.lst[child_idx] = self.lst[child_idx], self.lst[parent_idx]
self.heapify_up(parent_idx)


Testing:

heap = BinHeap()

heap.insert(4)
heap.insert(5)

print(heap.lst)

print(heap.pop_root())
print(heap.pop_root())

print(heap.lst)

###Output:
# [4, 5]
# 4
# 5
# []

heap.insert(4)
heap.insert(5)
heap.insert(3)
heap.insert(7)
heap.insert(9)
heap.insert(10)
heap.insert(2)

print(heap.lst)

print(heap.pop_root())
print(heap.lst)

heap.insert(1)
print(heap.lst)

###Output:
# [2, 5, 3, 7, 9, 10, 4]
# 2
# [3, 5, 4, 7, 9, 10]
# [1, 5, 3, 7, 9, 10, 4]