PROGRAM:
class Node:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
class BST:
def __init__(self):
[Link] = None
def insert(self, root, key):
if not root:
return Node(key)
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
return root
def search(self, root, key):
if not root or [Link] == key:
return root
return [Link]([Link], key) if key < [Link] else [Link]([Link], key)
def inorder(self, root):
if root:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
bst = BST()
root = None
# Insert elements into BST
elements = [50, 30, 70, 20, 40, 60, 80]
for key in elements:
root = [Link](root, key)
# Display BST in inorder traversal
print("Inorder Traversal of BST:")
[Link](root)
print()
# Search for keys
search_keys = [40, 100]
for key in search_keys:
result = [Link](root, key)
if result:
print(f"Search {key}: Found")
else:
print(f"Search {key}: Not Found")
PROGRAM:
class Node:
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None
class BST:
def __init__(self):
[Link] = None
def insert(self, root, key):
"""Insert a new key into the BST."""
if not root:
return Node(key)
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
return root
def printInorder(self, root):
"""Print the inorder traversal of BST."""
if root:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
arr = list(map(int, input("Enter N positive integers separated by space: ").split()))
bst = BST()
root = None
# Build BST (first element as root)
for num in arr:
root = [Link](root, num)
# Print Inorder Traversal
print("Inorder Traversal of BST:")
[Link](root)
print()
PROGRAM:
class AVLNode:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
[Link] = 1
class AVLTree:
def insert(self, root, key):
if not root:
return AVLNode(key)
if key < [Link]:
[Link] = [Link]([Link], key)
else:
[Link] = [Link]([Link], key)
# Update height
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
# Get balance factor
balance = [Link](root)
# Left Left Case
if balance > 1 and key < [Link]:
return [Link](root)
# Right Right Case
if balance < -1 and key > [Link]:
return [Link](root)
# Left Right Case
if balance > 1 and key > [Link]:
[Link] = [Link]([Link])
return [Link](root)
# Right Left Case
if balance < -1 and key < [Link]:
[Link] = [Link]([Link])
return [Link](root)
return root
def getHeight(self, node):
return [Link] if node else 0
def getBalance(self, node):
return [Link]([Link]) - [Link]([Link]) if node else 0
def leftRotate(self, z):
y = [Link]
T2 = [Link]
# Perform rotation
[Link] = z
[Link] = T2
# Update heights
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
return y
def rightRotate(self, y):
x = [Link]
T2 = [Link]
[Link] = y
[Link] = T2
# Update heights
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
[Link] = 1 + max([Link]([Link]), [Link]([Link]))
return x
def inorder(self, root):
if root:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
# -------------------------------
# Example Usage
# -------------------------------
avl = AVLTree()
root = None
keys = [10, 20, 30, 15, 50, 25] # Sample input
for key in keys:
root = [Link](root, key)
print("Inorder Traversal of Balanced AVL Tree:")
[Link](root)
print()
PROGRAM:
class MinHeap:
def __init__(self):
[Link] = []
def insert(self, patient_name, priority):
# Append new patient
[Link]((priority, patient_name))
self.__heapify_up(len([Link]) - 1)
def extract_min(self):
if not [Link]:
print("No patients in queue.")
return None
if len([Link]) == 1:
return [Link]()
# Root is min; replace with last element
min_patient = [Link][0]
[Link][0] = [Link]()
self.__heapify_down(0)
return min_patient
def __heapify_up(self, index):
parent = (index - 1) // 2
if index > 0 and [Link][index][0] < [Link][parent][0]:
[Link][index], [Link][parent] = [Link][parent], [Link][index]
self.__heapify_up(parent)
def __heapify_down(self, index):
left = 2 * index + 1
right = 2 * index + 2
smallest = index
if left < len([Link]) and [Link][left][0] < [Link][smallest][0]:
smallest = left
if right < len([Link]) and [Link][right][0] < [Link][smallest][0]:
smallest = right
if smallest != index:
[Link][smallest], [Link][index] = [Link][index], [Link][smallest]
self.__heapify_down(smallest)
def display(self):
print("Current ER Queue (Priority, Patient):")
for patient in [Link]:
print(f"Priority: {patient[0]} - Patient: {patient[1]}")
print()
er_queue = MinHeap()
# Insert patients
er_queue.insert("Alice", 5) # Less critical
er_queue.insert("Bob", 3) # Moderate case
er_queue.insert("Charlie", 1) # Most critical
er_queue.insert("David", 4)
er_queue.insert("Eva", 2)
# Display heap state
er_queue.display()
# Treat patients by extracting minimum (most severe first)
print("Treating patients in order of severity:")
while True:
patient = er_queue.extract_min()
if patient is None:
break
print(f"Treating: {patient[1]} (Severity: {patient[0]})")
PROGRAM:
def heapify(arr, n, i):
# Max heapify at index i
largest = i
left = 2 * i
right = 2 * i + 1
# Check left child
if left <= n and arr[left] > arr[largest]:
largest = left
# Check right child
if right <= n and arr[right] > arr[largest]:
largest = right
# Swap and continue heapifying if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def buildMaxHeap(arr, n):
# Start from last non-leaf node and go up to the root
for i in range(n // 2, 0, -1):
heapify(arr, n, i)
def heapSort(arr, n):
# Step 1: Build Max Heap
buildMaxHeap(arr, n)
# Step 2: Extract elements one by one
for i in range(n, 1, -1):
arr[1], arr[i] = arr[i], arr[1] # Swap max with last
heapify(arr, i - 1, 1) # Heapify reduced heap
# Input array (1-based indexing, so index 0 is dummy)
arr = [None] + [20, 5, 15, 22, 40, 10]
n = len(arr) - 1 # Ignore index 0
print("Original Array (1-based indexing):")
print(arr[1:])
# Perform Heap Sort
heapSort(arr, n)
print("\nElements in Descending Order after Heap Sort:")
print(arr[1:])
PROGRAM:
import heapq
def dijkstra(graph, start):
# Initialize distances with infinity
distances = {node: float('inf') for node in graph}
distances[start] = 0
visited = set()
# Min-heap for selecting shortest edge
heap = [(0, start)]
while heap:
curr_dist, curr_node = [Link](heap)
if curr_node in visited:
continue
[Link](curr_node)
for neighbor, weight in graph[curr_node].items():
distance = curr_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
[Link](heap, (distance, neighbor))
return distances
graph = {
'A': {'B': 5, 'C': 2},
'B': {'D': 1},
'C': {'B': 8, 'D': 7},
'D': {}
}
print("Shortest Distances from source A:")
print(dijkstra(graph, 'A'))
PROGRAM:
def find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i])
return parent[i]
def union(parent, rank, x, y):
xroot, yroot = find(parent, x), find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal(graph):
result = []
parent, rank = [], []
# Initialize disjoint sets
for node in range(len(graph)):
[Link](node)
[Link](0)
# Sort edges by weight
edges = sorted(graph, key=lambda item: item[2])
e = 0 # count of edges in MST
i = 0 # index variable for sorted edges
while e < len(graph) - 1 and i < len(edges):
u, v, w = edges[i]
i += 1
x, y = find(parent, u), find(parent, v)
if x != y:
e += 1
[Link]((u, v, w))
union(parent, rank, x, y)
return result
graph = [(0, 1, 10), (1, 2, 5), (0, 2, 6)]
print("Edges in MST:")
print(kruskal(graph))
PROGRAM:
from heapq import heappush, heappop
def prim(graph):
min_spanning_tree = []
visited = set()
# Start from an arbitrary vertex
start_vertex = list([Link]())[0]
# Initialize priority queue with edges of start_vertex
priority_queue = [(0, None, start_vertex)]
while priority_queue:
weight, parent, current_vertex = heappop(priority_queue)
if current_vertex not in visited:
[Link](current_vertex)
if parent is not None:
min_spanning_tree.append((parent, current_vertex, weight))
for neighbor, edge_weight in graph[current_vertex]:
if neighbor not in visited:
heappush(priority_queue, (edge_weight, current_vertex, neighbor))
return min_spanning_tree
graph = {
'A': [('B', 2), ('C', 1)],
'B': [('A', 2), ('D', 3), ('E', 1)],
'C': [('A', 1), ('D', 4)],
'D': [('B', 3), ('C', 4), ('E', 1)],
'E': [('B', 1), ('D', 1)]
}
minimum_spanning_tree = prim(graph)
print("Minimum Spanning Tree:")
print(minimum_spanning_tree)