About
lass BinHeap: def _init_(self): self.heapList = [0] self.sz = 0
def upHeap(self, i):
while i // 2 > 0:
if self.heapList[i] > self.heapList[i // 2]:
self.heapList[i], self.heapList[i // 2] = self.heapList[i // 2], self.heapList[i]
i = i // 2
def insert(self, k):
self.heapList.append(k)
self.sz += 1
i = self.sz
while i > 1 and self.heapList[i] > self.heapList[i // 2]:
self.heapList[i], self.heapList[i // 2] = self.heapList[i // 2], self.heapList[i]
i = i // 2
self.printHeap()
def downHeap(self, i):
while (i * 2) <= self.sz:
mc = self.maxChild(i)
if self.heapList[i] < self.heapList[mc]:
self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]
i = mc
def maxChild(self, i):
if i * 2 + 1 > self.sz:
return i * 2
else:
if self.heapList[i * 2] > self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def deleteOp(self):
if self.sz == 0:
return None
max_val = self.heapList[1]
self.heapList[1] = self.heapList[self.sz]
self.sz -= 1
self.heapList.pop()
self.downHeap(1)
self.printHeap()
return max_val
def buildHeap(self, alist):
self.heapList = [0]
self.sz = 0
for item in alist:
self.insert(item)
def printHeap(self):
print("Heap contents:", self.heapList[1:])
def kLargest(self, k):
if k <= self.sz:
return sorted(self.heapList[1:], reverse=True)[k - 1]
else:
return None
def deleteElement(self,e):
if self.sz == 0:
return None
try:
index = self.heapList.index(e)
except ValueError:
print(f"Element {e} not found in the heap.")
return None
self.heapList[index] = self.heapList[self.sz]
self.sz -= 1
self.heapList.pop()
if index <= self.sz:
self.downHeap(index)
self.upHeap(index)
self.printHeap()
return edef main(): heap = BinHeap() arraysize = int(input("Enter the size of the array: ")) arr = list(map(int, input("Enter the array elements: ").split())) k = int(input("Enter the value of k: ")) heap.buildHeap(arr) inputs = int(input("Enter the number of operations: ")) while inputs > 0: command = input("Enter command: ") operation = command.split() if operation[0] == "I": heap.insert(int(operation[1]))
elif operation[0] == "D":
heap.deleteOp()
elif operation[0] == "X":
element = int(operation[1])
heap.deleteElement(element)
elif operation[0] == "K":
kthLargest = heap.kLargest(k)
if kthLargest is not None:
print(f"The {k}-th largest element is: {kthLargest}")
else:
print(f"No {k}-th largest element exists.")
inputs -= 1if _name_ == '_main_': main()
import math class BinarySearchTree: class node: def _init_(self): self.element = 0 self.leftchild = None self.rightchild = None self.pos = -1 self.parent = None
def _init_(self):
self.sz = 0
self.root = None
self.ht = 0
def findElement(self, e, curnode):
if curnode is None or curnode.element == e:
return curnode
if e < curnode.element:
return self.findElement(e, curnode.leftchild)
else:
return self.findElement(e, curnode.rightchild)
def insertElement(self, e):
newNode = self.node()
newNode.element = e
newNode.pos = 1
if self.root is None:
self.root = newNode
else:
cur = self.root
while True:
if e < cur.element:
if cur.leftchild is None:
cur.leftchild = newNode
newNode.parent = cur
newNode.pos = cur.pos * 2
break
else:
cur = cur.leftchild
else:
if cur.rightchild is None:
cur.rightchild = newNode
newNode.parent = cur
newNode.pos = cur.pos * 2 + 1
break
else:
cur = cur.rightchild
self.sz += 1
def inorderTraverse(self, v):
if v:
self.inorderTraverse(v.leftchild)
print(v.element, end=" ")
self.inorderTraverse(v.rightchild)
def returnNextInorder(self, v):
if v.rightchild:
return self.findMin(v.rightchild)
p = v.parent
while p and v == p.rightchild:
v = p
p = p.parent
return p
def deleteElement(self, e):
self.root = self.remove(self.root, e)
def remove(self, root, e):
if root is None:
return root
if e < root.element:
root.leftchild = self.remove(root.leftchild, e)
elif e > root.element:
root.rightchild = self.remove(root.rightchild, e)
else:
if root.leftchild is None:
temp = root.rightchild
root = None
return temp
elif root.rightchild is None:
temp = root.leftchild
root = None
return temp
temp = self.findMin(root.rightchild)
root.element = temp.element
root.rightchild = self.remove(root.rightchild, temp.element)
return root
def findMin(self, root):
current = root
while current.leftchild is not None:
current = current.leftchild
return current
def isExternal(self, curnode):
if curnode.leftchild is None and curnode.rightchild is None:
return True
else:
return False
def getChildren(self, ele):
node = self.findElement(ele, self.root)
children = []
if node.leftchild:
children.append(node.leftchild.element)
if node.rightchild:
children.append(node.rightchild.element)
return children
def preorderTraverse(self, v):
if v:
print(v.element, end=" ")
self.preorderTraverse(v.leftchild)
self.preorderTraverse(v.rightchild)
def postorderTraverse(self, v):
if v:
self.postorderTraverse(v.leftchild)
self.postorderTraverse(v.rightchild)
print(v.element, end=" ")
def findDepthIter(self, v):
depth = 0
while v.parent:
depth += 1
v = v.parent
return depth
def findDepth(self, ele):
curnode = self.findElement(ele, self.root)
if curnode.element != ele:
print("No such Element")
return
else:
return self.findDepthIter(curnode)
def findHeight(self, ele):
curnode = self.findElement(ele, self.root)
if curnode is None:
return -1
else:
return self.calcHeight(curnode)
def calcHeight(self, node):
if node is None:
return -1
left_height = self.calcHeight(node.leftchild)
right_height = self.calcHeight(node.rightchild)
return max(left_height, right_height) + 1def main(): tree = BinarySearchTree()
#print("Array Size:")
arraySize = int(input())
#print("Array Elements:")
arr = list(map(int, input().split()))
for i in range(arraySize):
tree.insertElement(arr[i])
"""tree.insertElement(50)
tree.insertElement(20)
tree.insertElement(70)
tree.insertElement(1)
tree.insertElement(10)
tree.insertElement(90)
tree.insertElement(15)
tree.insertElement(30)
tree.insertElement(60)
tree.insertElement(61)
tree.insertElement(62)
tree.insertElement(65)
tree.insertElement(8)
tree.insertElement(100)"""
inputs = int(input())
while inputs > 0:
command = input()
operation = command.split()
if operation[0] == "I":
tree.inorderTraverse(tree.root)
print()
elif operation[0] == "P":
tree.preorderTraverse(tree.root)
print()
elif operation[0] == "Post":
tree.postorderTraverse(tree.root)
print()
elif operation[0] == "D":
tree.deleteElement(int(operation[1]))
elif operation[0] == "H":
print(tree.findHeight(int(operation[1])))
elif operation[0] == "Depth":
print(tree.findDepth(int(operation[1])))
elif operation[0] == 'Find':
key = tree.findElement(int(operation[1]), tree.root)
if key and key.element == int(operation[1]):
print("Element Found at", key.pos)
else:
print("Element not Found")
elif operation[0] == "GetC":
childs = tree.getChildren(int(operation[1]))
print(childs)
inputs -= 1if _name_ == '_main_': main()