I wrote a min-heap using a binary tee. How can I improve the time complexity of insert and delete function to log(n)? Thank you
'''
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()
