Min Heap Tree Implementation in python 3

Question

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):
 self.head = None
 def insert(self, data):
 if self.head is None:
 self.head = Node(data)
 return
 lst = []
 lst.append(self.head)
 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):
 if self.head is None:
 return
 lst = []
 lst.append(self.head)
 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 = []
 lst.append(self.head)
 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):
 if self.head is None:
 return 'Heap is empty.'
 data = self.head.data
 if self.head.left is None and self.head.right is None:
 self.head = None
 return data
 lst = []
 lst.append(self.head)
 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 = []
 lst.append(self.head)
 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)
 self.head.data = leafData
 self.heapifyTopDown(self.head)
 return data
 def peek(self):
 if self.head is None:
 return 'self.head is None'
 return self.head.data
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()

• Christopher Boo: 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.

Answer 1

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]