Name: ANVITHA

RegNo.: 251090840007

LAB PROGRAM 1

1. Write a program that allows the user to insert an element at the top of the stack, remove the element
currently at the top, view the top element without removing it, and display all elements present in the
stack.
• Handle stack overflow and stack underflow conditions with appropriate error messages.
• Accept the maximum size of the stack as user input.
• Display the time complexity of each operation.
• Execute the program for different stack sizes and record the execution times for push and pop
operations to analyse performance.

import java.util.Scanner;
class Stack {
int[] arr;
int top;
int maxSize;
Stack(int size) {
maxSize = size;
arr = new int[maxSize];
top = -1;
}

void push(int value) {

if (top == maxSize - 1) {
System.out.println("Stack Overflow! Cannot push " + value);
} else {
arr[++top] = value;
System.out.println(value + " pushed into the stack.");
}
}

void pop() {
if (top == -1) {
System.out.println("Stack Underflow! No element to pop.");
} else {
System.out.println(arr[top--] + " popped from the stack.");
}
}

void peek() {
if (top == -1) {
 System.out.println("Stack is empty. Nothing to peek.");
} else {
System.out.println("Top element is: " + arr[top]);
}
}

void display() {
if (top == -1) {
System.out.println("Stack is empty.");
} else {
System.out.print("Stack elements: ");
for (int i = 0; i <= top; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
}

public class StackDemo {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the maximum size of the stack: ");
int size = sc.nextInt();
Stack stack = new Stack(size);
int choice;
do {
System.out.println("1. Push");
System.out.println("2. Pop");
System.out.println("3. Peek");
System.out.println("4. Display");
System.out.println("5. Exit");
System.out.print("Enter your choice: ");
choice = sc.nextInt();
switch (choice) {
case 1:
System.out.print("Enter element to push: ");
int val = sc.nextInt();
stack.push(val);
break;
case 2:
stack.pop();
break;
case 3:
stack.peek();
break;
case 4:
stack.display();
break;
case 5:
System.out.println("Exiting program...");
break;
default:
System.out.println("Invalid choice! Please try again.");
 }
} while (choice != 5);
sc.close();
}
}

OUTPUT
2. Write a program that allows the user to add an element to the end of the queue, remove an element
from the front, view the element at the front without removing it, and display all elements currently in
the queue.
• Handle queue overflow and underflow conditions with appropriate error messages.
• Accept the maximum size of the queue as user input.
• Display the time complexity of each operation.
• Execute the program for different queue sizes and record the execution times for inserting and
removing elements to analyse performance.

import java.util.Scanner;
public class QueueProgram {
private int[] queue;
private int front, rear, size, capacity;

public QueueProgram(int capacity) {

this.capacity = capacity;
queue = new int[capacity];
front = 0;
rear = -1;
size = 0;
}

public boolean isFull() {

return size == capacity;
}

public boolean isEmpty() {

return size == 0;
}

public void enqueue(int element) {

if (isFull()) {
System.out.println("Queue Overflow! Cannot add element.");
return;
}
rear = (rear + 1) % capacity;
queue[rear] = element;
size++;
System.out.println("Inserted: " + element);
}

public void dequeue() {

if (isEmpty()) {
System.out.println("Queue Underflow! Cannot remove element.");
return;
}
System.out.println("Removed: " + queue[front]);
front = (front + 1) % capacity;
 size--;
}

public void peek() {

if (isEmpty()) {
System.out.println("Queue is empty.");
} else {
System.out.println("Front element: " + queue[front]);
}
}

public void display() {

if (isEmpty()) {
System.out.println("Queue is empty.");
return;
}
System.out.print("Queue elements: ");
for (int i = 0; i < size; i++) {
System.out.print(queue[(front + i) % capacity] + " ");
}
System.out.println();
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
System.out.print("Enter maximum size of the queue: ");
int maxSize = sc.nextInt();
QueueProgram q = new QueueProgram(maxSize);
while (true) {
System.out.println("\n1. Enqueue\n2. Dequeue\n3. Peek\n4. Display\n5.
Exit");
System.out.print("Choose an option: ");
int choice = sc.nextInt();
long startTime, endTime;

switch (choice) {
case 1:
System.out.print("Enter element to insert: ");
int element = sc.nextInt();
startTime = System.nanoTime();
q.enqueue(element);
break;
case 2:
startTime = System.nanoTime();
q.dequeue();
break;
case 3:
q.peek();
break;
case 4:
q.display();
break;
case 5:
System.out.println("Exiting program.");
 sc.close();
return;
default:
System.out.println("Invalid choice.");
}
}
}
}

OUTPUT
 LAB PROGRAM 2

1. Design and implement a menu-driven Java/C/C++ program to perform stack operations using a
singly linked list. The program should allow the user to:
• Insert an element into the stack (Push).
• Remove the top element from the stack (Pop) with proper underflow handling.
• Retrieve the top element without removing it (Peek).
• Check whether the stack is empty (isEmpty).
• Display all the elements of the stack from top to bottom (Display).

import java.util.Scanner;
class Node {
int data;
Node next;
}
class StackLinkedList {
private Node top;
public StackLinkedList() {
top = null;
}
public boolean isEmpty() {
return top == null;
}
public void push(int value) {
Node newNode = new Node();
newNode.data = value;
newNode.next = top;
top = newNode;
System.out.println("Pushed: " + value);
}
public void pop() {
if (isEmpty()) {
System.out.println("Stack Underflow! Cannot pop.");
} else {
System.out.println("Popped: " + top.data);
top = top.next;
}
}
public void peek() {
if (isEmpty()) {
System.out.println("Stack is empty.");
} else {
System.out.println("Top element: " + top.data);
}
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty.");
} else {
 System.out.println("Stack elements (top to bottom):");
Node temp = top;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
}
}
public class StackMenu {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StackLinkedList stack = new StackLinkedList();
while (true) {
System.out.println("\n1. Push\n2. Pop\n3. Peek\n4. isEmpty\n5.
Display\n6. Exit");
System.out.print("Enter your choice: ");
int choice = sc.nextInt();
switch (choice) {
case 1:
System.out.print("Enter element to push: ");
int value = sc.nextInt();
stack.push(value);
break;
case 2:
stack.pop();
break;
case 3:
stack.peek();
break;
case 4:
System.out.println(stack.isEmpty() ? "Stack is empty." :
"Stack is not empty.");
break;
case 5:
stack.display();
break;
case 6:
System.out.println("Exiting program.");
sc.close();
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
}
OUTPUT
2. Design and implement a menu-driven Java/C/C++ program to perform queue operations using a
singly linked list. The program should allow the user to:
• Insert an element at the rear (Enqueue). Remove the element from the front (Dequeue) with
proper underflow handling.
• Retrieve (peek) the front element without removing it (Front/Peek).
• Check whether the queue is empty (isEmpty).
• Display all the elements of the queue from front to rear (Display).
• Note: Maintain front and rear pointers for O(1) enqueue/dequeue. On first insert, set both
front and rear to the new node; when the last node is dequeued, set both to NULL.

import java.util.Scanner;
class Node {
int data;
Node next;
}

class QueueLinkedList {
private Node front, rear;
public QueueLinkedList() {
front = rear = null;
}

public boolean isEmpty() {

return front == null;
}

public void enqueue(int value) {

Node newNode = new Node();
newNode.data = value;
newNode.next = null;

if (isEmpty()) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}

System.out.println("Enqueued: " + value);

}

public void dequeue() {

if (isEmpty()) {
System.out.println("Queue Underflow! Cannot dequeue.");
} else {
System.out.println("Dequeued: " + front.data);
front = front.next;
if (front == null) {
rear = null;
}
 }
}

public void peek() {

if (isEmpty()) {
System.out.println("Queue is empty.");
} else {
System.out.println("Front element: " + front.data);
}
}

public void display() {

if (isEmpty()) {
System.out.println("Queue is empty.");
} else {
System.out.println("Queue elements (front to rear):");
Node temp = front;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
}
}
public class QueueMenu {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
QueueLinkedList queue = new QueueLinkedList();
while (true) {
System.out.println("\n1. Enqueue\n2. Dequeue\n3. Peek\n4. isEmpty\n5.
Display\n6. Exit");
System.out.print("Enter your choice: ");
int choice = sc.nextInt();
switch (choice) {
case 1:
System.out.print("Enter element to enqueue: ");
int value = sc.nextInt();
queue.enqueue(value);
break;
case 2:
queue.dequeue();
break;
case 3:
queue.peek();
break;
case 4:
System.out.println(queue.isEmpty() ? "Queue is empty." :
"Queue is not empty.");
break;
case 5:
queue.display();
break;
case 6:
System.out.println("Exiting program.");
 sc.close();
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
}

OUTPUT
 LAB PROGRAM – 3

1. A music streaming application needs to maintain a playlist where users can play songs in both
forward and backward directions. To support this, the application should use a doubly linked list
where each node stores the song title. The structure should allow adding new songs to the playlist,
removing songs, and displaying the playlist in both forward and reverse order. Since a doubly
linked list maintains links in both directions, it becomes easy for the user to navigate back and
forth across the songs, delete specific songs, or insert new ones at desired positions.

import java.util.Scanner;
class SongNode {
String title;
SongNode prev, next;
public SongNode(String title) {
this.title = title;
this.prev = null;
this.next = null;
}
}
class Playlist {
private SongNode head, tail;
public Playlist() {
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
public void addSong(String title) {
SongNode newNode = new SongNode(title);
if (isEmpty()) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
System.out.println("Added: " + title);
}
public void removeSong(String title) {
if (isEmpty()) {
System.out.println("Playlist is empty. No songs to remove.");
return;
}
SongNode current = head;
while (current != null) {
if (current.title.equalsIgnoreCase(title)) {
if (current == head) {
head = head.next;
if (head != null) head.prev = null;
else tail = null;
} else if (current == tail) {
 tail = tail.prev;
tail.next = null;
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
System.out.println("Removed: " + title);
return;
}
current = current.next;
}
System.out.println("Song not found: " + title);
}
public void displayForward() {
if (isEmpty()) {
System.out.println("Playlist is empty.");
return;
}
System.out.println("Playlist (Forward):");
SongNode current = head;
while (current != null) {
System.out.println(current.title);
current = current.next;
}
}
public void displayBackward() {
if (isEmpty()) {
System.out.println("Playlist is empty.");
return;
}
System.out.println("Playlist (Backward):");
SongNode current = tail;
while (current != null) {
System.out.println(current.title);
current = current.prev;
}
}
}
public class MusicPlaylistApp {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Playlist playlist = new Playlist();
while (true) {
System.out.println("\n1. Add Song\n2. Remove Song\n3. Display
Forward\n4. Display Backward\n5. Exit");
System.out.print("Enter your choice: ");
int choice = sc.nextInt();
sc.nextLine(); // consume newline
switch (choice) {
case 1:
System.out.print("Enter song title to add: ");
String titleToAdd = sc.nextLine();
playlist.addSong(titleToAdd);
break;
 case 2:
if (playlist.isEmpty()) {
System.out.println("Playlist is empty. No songs to
remove.");
} else {
System.out.print("Enter song title to remove: ");
String titleToRemove = sc.nextLine();
playlist.removeSong(titleToRemove);
}
break;
case 3:
playlist.displayForward();
break;
case 4:
playlist.displayBackward();
break;
case 5:
System.out.println("Exiting program.");
sc.close();
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
}

OUTPUT
3. A university library is designing a system to maintain its digital catalog of journal IDs. Since the
catalog is frequently updated with new journals being added and outdated ones being removed, the
data structure must support efficient insertion and searching while keeping the catalog balanced to
avoid performance degradation. To achieve this, the system should be implemented using an AVL Tree,
a self-balancing binary search tree where the heights of the left and right subtrees of any node differ
by at most one. The program should also allow traversal of the AVL tree (inorder, preorder, postorder)
to display the catalog in sorted or hierarchical order.

import java.util.Scanner;
class AVLNode {
int journalID;
int height;
AVLNode left, right;

AVLNode(int id) {
journalID = id;
height = 1;
}
}

class AVLTree {
private AVLNode root;
int height(AVLNode node) {
return node == null ? 0 : node.height;
}
int getBalance(AVLNode node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}

AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}

AVLNode insert(AVLNode node, int id) {

if (node == null)
return new AVLNode(id);
 if (id < node.journalID)
node.left = insert(node.left, id);
else if (id > node.journalID)
node.right = insert(node.right, id);
else
return node; // Duplicate IDs not allowed

node.height = 1 + Math.max(height(node.left), height(node.right));

int balance = getBalance(node);

if (balance > 1 && id < node.left.journalID)

return rightRotate(node);
if (balance < -1 && id > node.right.journalID)
return leftRotate(node);
if (balance > 1 && id > node.left.journalID) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && id < node.right.journalID) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}

void insert(int id) {

root = insert(root, id);
}
boolean search(AVLNode node, int id) {
if (node == null)
return false;
if (id == node.journalID)
return true;
return id < node.journalID ? search(node.left, id) : search(node.right, id);
}
boolean search(int id) {
return search(root, id);
}
void inorder(AVLNode node) {
if (node != null) {
inorder(node.left);
System.out.print(node.journalID + " ");
inorder(node.right);
}
}

void preorder(AVLNode node) {

if (node != null) {
System.out.print(node.journalID + " ");
preorder(node.left);
preorder(node.right);
}
}
 void postorder(AVLNode node) {
if (node != null) {
postorder(node.left);
postorder(node.right);
System.out.print(node.journalID + " ");
}
}

void display(String type) {

switch (type.toLowerCase()) {
case "inorder":
inorder(root);
break;
case "preorder":
preorder(root);
break;
case "postorder":
postorder(root);
break;
default:
System.out.println("Invalid traversal type.");
}
System.out.println();
}
}

public class LibraryCatalog {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
AVLTree tree = new AVLTree();
int choice;
do {
System.out.println("1. Insert Journal ID");
System.out.println("2. Search Journal ID");
System.out.println("3. Display Catalog (Inorder)");
System.out.println("4. Display Catalog (Preorder)");
System.out.println("5. Display Catalog (Postorder)");
System.out.println("0. Exit");
System.out.print("Enter your choice: ");
choice = sc.nextInt();
switch (choice) {
case 1:
System.out.print("Enter Journal ID to insert: ");
int id = sc.nextInt();
tree.insert(id);
break;
case 2:
System.out.print("Enter Journal ID to search: ");
int searchID = sc.nextInt();
System.out.println(tree.search(searchID) ? "Journal found." :
"Journal not found.");
break;
case 3:
System.out.println("Inorder Traversal:");
 tree.display("inorder");
break;
case 4:
System.out.println("Preorder Traversal:");
tree.display("preorder");
break;
case 5:
System.out.println("Postorder Traversal:");
tree.display("postorder");
break;
case 0:
System.out.println("Exiting...");
break;
default:
System.out.println("Invalid choice.");
}
} while (choice != 0);
sc.close();
}
}

OUTPUT
 LAB PROGRAM – 4
1. Design and implement a menu-driven Java program to construct and manipulate an expression tree for
a given arithmetic expression. The program should allow the user to build the tree from a valid infix
or postfix expression, where internal nodes represent operators and leaf nodes represent operands.
Once the expression tree is constructed, the program should support evaluating the expression
represented by the tree and displaying it in different traversal orders to obtain prefix, infix, and postfix
forms. It should also provide functionality to check whether the tree is empty, handle invalid
expressions with appropriate messages, and display the tree structure clearly. The implementation
should demonstrate how expression trees can be used for parsing and evaluating arithmetic expressions
efficiently in compilers and interpreters.

import java.util.*;

// Node class for Expression Tree

class Node {
String data;
Node left, right;

Node(String data) {
this.data = data;
left = right = null;
}
}

class ExpressionTree {
Node root;

// Check if operator
private boolean isOperator(String s) {
return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
}

// Build tree from postfix expression

public void buildTree(String postfix) {
Stack<Node> stack = new Stack<>();
String[] tokens = postfix.split(" ");

for (String token : tokens) {

if (!isOperator(token)) { // Operand
stack.push(new Node(token));
} else { // Operator
Node right = stack.pop();
Node left = stack.pop();
Node newNode = new Node(token);
newNode.left = left;
newNode.right = right;
stack.push(newNode);
}
}
root = stack.pop();
}
// Traversals
public void printInfix(Node node) {
if (node != null) {
if (isOperator(node.data))
System.out.print("( ");
printInfix(node.left);
System.out.print(node.data + " ");
printInfix(node.right);
if (isOperator(node.data))
System.out.print(") ");
}
}

public void printPrefix(Node node) {

if (node != null) {
System.out.print(node.data + " ");
printPrefix(node.left);
printPrefix(node.right);
}
}

public void printPostfix(Node node) {

if (node != null) {
printPostfix(node.left);
printPostfix(node.right);
System.out.print(node.data + " ");
}
}

// Evaluate or simplify expression

public String evaluate(Node node) {
if (node == null)
return "";

// If it's an operand
if (!isOperator(node.data)) {
// Check if it's a number
try {
Integer.parseInt(node.data); // test conversion
return node.data; // return as number string
} catch (NumberFormatException e) {
return node.data; // return variable like "a"
}
}

// Recursive evaluation
String leftVal = evaluate(node.left);
String rightVal = evaluate(node.right);

// If both are numbers, calculate

try {
int leftNum = Integer.parseInt(leftVal);
int rightNum = Integer.parseInt(rightVal);
 switch (node.data) {
case "+":
return String.valueOf(leftNum + rightNum);
case "-":
return String.valueOf(leftNum - rightNum);
case "*":
return String.valueOf(leftNum * rightNum);
case "/":
return String.valueOf(leftNum / rightNum);
}
} catch (NumberFormatException e) {
// If not numbers, keep symbolic
}

return "(" + leftVal + " " + node.data + " " + rightVal + ")";
}
}

public class ExpressionTreeSimple {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ExpressionTree tree = new ExpressionTree();

System.out.println("Enter Postfix Expression (with spaces): ");

String postfix = sc.nextLine();

tree.buildTree(postfix);

System.out.print("Infix: ");
tree.printInfix(tree.root);
System.out.println();

System.out.print("Prefix: ");
tree.printPrefix(tree.root);
System.out.println();

System.out.print("Postfix: ");
tree.printPostfix(tree.root);
System.out.println();

System.out.println("Evaluated/Simplified Expression: " +

tree.evaluate(tree.root));

sc.close();
}
}
2. Design and implement a menu-driven Java program to perform operations on a multi-way search tree
suitable for indexing large amounts of data. The tree should allow multiple keys to be stored in a single
node and should maintain balance automatically during insertions and deletions by redistributing or
merging keys when required. The program should support inserting new keys, deleting existing keys,
and searching for a given key efficiently. It should also provide options to traverse and display the
contents of the tree in sorted order and in level-wise structure to visualize the hierarchy. The
implementation must ensure that the tree remains balanced after every update so that search, insert,
and delete operations can always be performed in logarithmic time. Proper messages should be
displayed for unsuccessful search or delete operations, and the program should be tested with a set of
sample keys to demonstrate how the structure grows and shrinks dynamically.
3. import java.util.*;
4.
5. /**
6. * B-Tree implementation (minimum degree t).
7. * Supports insert, search, delete (full implementation),
8. * inorder (sorted) traverse and level-order display.
9. *
10. * Single-file program with a simple menu in main().
11. *
12. * Compile: javac BTreeMenu.java
13. * Run: java BTreeMenu
14. */
15. class BTreeNode {
16. int[] keys; // keys array
17. int t; // minimum degree
18. BTreeNode[] children; // child pointers
19. int n; // current number of keys
20. boolean leaf; // is true when node is leaf
21.
22. BTreeNode(int t, boolean leaf) {
23. this.t = t;
24. this.leaf = leaf;
25. this.keys = new int[2 * t - 1];
26. this.children = new BTreeNode[2 * t];
27. this.n = 0;
28. }
29.
30. // Traverse the subtree rooted with this node (inorder)
31. void traverse() {
32. int i;
33. for (i = 0; i < n; i++) {
34. if (!leaf)
35. children[i].traverse();
36. System.out.print(keys[i] + " ");
37. }
38. if (!leaf)
39. children[i].traverse();
40. }
41.
42. // Search key k in subtree rooted with this node
43. BTreeNode search(int k) {
44. int i = 0;
45. while (i < n && k > keys[i]) i++;
46.
47. if (i < n && keys[i] == k) return this;
48.
49. if (leaf) return null;
50.
51. return children[i].search(k);
52. }
53.
54. // A utility function to insert a new key in this node
55. // The node must be non-full when this function is called
56. void insertNonFull(int k) {
57. int i = n - 1;
58.
59. if (leaf) {
60. // Shift keys to make space
61. while (i >= 0 && keys[i] > k) {
62. keys[i + 1] = keys[i];
63. i--;
64. }
65. keys[i + 1] = k;
66. n = n + 1;
67. } else {
68. // Find the child which is going to have the new key
69. while (i >= 0 && keys[i] > k) i--;
70. i++;
71.
72. // If the found child is full, split it
73. if (children[i].n == 2 * t - 1) {
74. splitChild(i, children[i]);
75.
76. // After split, the middle key of children[i] goes up and
children[i] is split into two.
77. // See which of the two is going to have the new key
78. if (keys[i] < k)
79. i++;
80. }
81. children[i].insertNonFull(k);
82. }
83. }
84.
85. // Split the child y of this node. i is index of y in child array children[]
86. void splitChild(int i, BTreeNode y) {
87. BTreeNode z = new BTreeNode(y.t, y.leaf);
88. z.n = t - 1;
89.
90. // Copy last (t-1) keys of y to z
91. for (int j = 0; j < t - 1; j++)
92. z.keys[j] = y.keys[j + t];
93.
94. // Copy the last t children of y to z
95. if (!y.leaf) {
96. for (int j = 0; j < t; j++)
97. z.children[j] = y.children[j + t];
98. }
99.
100. // Reduce the number of keys in y
101. y.n = t - 1;
102.
103. // Create space for new child
104. for (int j = n; j >= i + 1; j--)
105. children[j + 1] = children[j];
106.
107. // Link new child to this node
108. children[i + 1] = z;
109.
110. // Move keys to make space for middle key of y
111. for (int j = n - 1; j >= i; j--)
112. keys[j + 1] = keys[j];
113.
114. // Copy the middle key of y to this node
115. keys[i] = y.keys[t - 1];
116.
117. // Increment key count of this node
118. n = n + 1;
119. }
120.
121. // Remove key k from subtree rooted with this node
122. void remove(int k) {
123. int idx = findKey(k);
124.
125. if (idx < n && keys[idx] == k) {
126. // The key to be removed is present in this node
127. if (leaf)
128. removeFromLeaf(idx);
129. else
130. removeFromNonLeaf(idx);
131. } else {
132. // If this node is a leaf node, then the key is not present in
tree
133. if (leaf) {
134. System.out.println("The key " + k + " is NOT present in the
tree.");
135. return;
136. }
137.
138. // The key to be removed is present in the sub-tree rooted with
this node
139. // The flag indicates whether the key is present in the sub-tree
rooted with last child of this node
140. boolean flag = (idx == n);
141.
142. // If the child where the key is supposed to exist has less that t
keys, we fill that child
143. if (children[idx].n < t)
144. fill(idx);
145.
146. // If the last child has been merged, it must have merged with the
previous child and so we recurse on (idx-1)th child.
147. // Else, we recurse on (idx)th child which now has at least t keys
148. if (flag && idx > n)
149. children[idx - 1].remove(k);
150. else
151. children[idx].remove(k);
152. }
153. }
154.
155. // Find index of first key greater than or equal to k
156. int findKey(int k) {
157. int idx = 0;
158. while (idx < n && keys[idx] < k)
159. ++idx;
160. return idx;
161. }
162.
163. void removeFromLeaf(int idx) {
164. // Move all keys after idx one place backward
165. for (int i = idx + 1; i < n; ++i)
166. keys[i - 1] = keys[i];
167. n--;
168. }
169.
170. void removeFromNonLeaf(int idx) {
171. int k = keys[idx];
172.
173. // If the child that precedes k (children[idx]) has at least t keys,
174. // find the predecessor 'pred' of k in the subtree rooted at
children[idx].
175. // Replace k by pred. Recursively delete pred in children[idx]
176. if (children[idx].n >= t) {
177. int pred = getPredecessor(idx);
178. keys[idx] = pred;
179. children[idx].remove(pred);
180. }
181. // If the child children[idx] has less than t keys, examine
children[idx+1].
182. // If children[idx+1] has at least t keys, find successor 'succ' of k
in children[idx+1]
183. // Replace k by succ. Recursively delete succ in children[idx+1]
184. else if (children[idx + 1].n >= t) {
185. int succ = getSuccessor(idx);
186. keys[idx] = succ;
187. children[idx + 1].remove(succ);
188. }
189. // If both children[idx] and children[idx+1] have less than t keys,
190. // merge k and all of children[idx+1] into children[idx]. Now
children[idx] contains 2t-1 keys.
191. // Free children[idx+1] and recursively delete k from children[idx]
192. else {
193. merge(idx);
194. children[idx].remove(k);
195. }
196. }
197.
198. int getPredecessor(int idx) {
199. // Keep moving to the rightmost node until we reach a leaf
200. BTreeNode cur = children[idx];
201. while (!cur.leaf)
202. cur = cur.children[cur.n];
203. return cur.keys[cur.n - 1];
204. }
205.
206. int getSuccessor(int idx) {
207. // Keep moving the leftmost node starting from children[idx+1] until
we reach a leaf
208. BTreeNode cur = children[idx + 1];
209. while (!cur.leaf)
210. cur = cur.children[0];
211. return cur.keys[0];
212. }
213.
214. // Fill child children[idx] which has less than t-1 keys
215. void fill(int idx) {
216. // If the previous child(children[idx-1]) has more than t-1 keys,
borrow a key from that child
217. if (idx != 0 && children[idx - 1].n >= t)
218. borrowFromPrev(idx);
219.
220. // If the next child(children[idx+1]) has more than t-1 keys, borrow a
key from that child
221. else if (idx != n && children[idx + 1].n >= t)
222. borrowFromNext(idx);
223.
224. // Merge children[idx] with its sibling
225. // If children[idx] is the last child, merge it with its previous
sibling
226. // Otherwise merge it with its next sibling
227. else {
228. if (idx != n)
229. merge(idx);
230. else
231. merge(idx - 1);
232. }
233. }
234.
235. // Borrow a key from children[idx-1] and insert it into children[idx]
236. void borrowFromPrev(int idx) {
237. BTreeNode child = children[idx];
238. BTreeNode sibling = children[idx - 1];
239.
240. // Moving all keys in child one step ahead
241. for (int i = child.n - 1; i >= 0; --i)
242. child.keys[i + 1] = child.keys[i];
243.
244. // If child is not leaf, move all its child pointers one step ahead
245. if (!child.leaf) {
246. for (int i = child.n; i >= 0; --i)
247. child.children[i + 1] = child.children[i];
248. }
249.
250. // Setting child's first key equal to keys[idx-1] from current node
251. child.keys[0] = keys[idx - 1];
252.
253. // Moving sibling's last child as child's first child
254. if (!child.leaf)
255. child.children[0] = sibling.children[sibling.n];
256.
257. // Move the last key from sibling to parent
258. keys[idx - 1] = sibling.keys[sibling.n - 1];
259.
260. child.n += 1;
261. sibling.n -= 1;
262. }
263.
264. // Borrow a key from children[idx+1] and place it in children[idx]
265. void borrowFromNext(int idx) {
266. BTreeNode child = children[idx];
267. BTreeNode sibling = children[idx + 1];
268.
269. // keys[idx] is inserted as the last key in child
270. child.keys[child.n] = keys[idx];
271.
272. // Sibling's first child is inserted as the last child into child
273. if (!child.leaf)
274. child.children[child.n + 1] = sibling.children[0];
275.
276. // First key from sibling is inserted into keys[idx]
277. keys[idx] = sibling.keys[0];
278.
279. // Move all keys in sibling one step behind
280. for (int i = 1; i < sibling.n; ++i)
281. sibling.keys[i - 1] = sibling.keys[i];
282.
283. // Move the child pointers one step behind
284. if (!sibling.leaf) {
285. for (int i = 1; i <= sibling.n; ++i)
286. sibling.children[i - 1] = sibling.children[i];
287. }
288.
289. child.n += 1;
290. sibling.n -= 1;
291. }
292.
293. // Merge children[idx] and children[idx+1]. keys[idx] moves down and
becomes the median key of merged node
294. void merge(int idx) {
295. BTreeNode child = children[idx];
296. BTreeNode sibling = children[idx + 1];
297.
298. // Pulling a key from the current node and inserting it into (t-1)th
position of child
299. child.keys[t - 1] = keys[idx];
300.
301. // Copying the keys from sibling to child
302. for (int i = 0; i < sibling.n; ++i)
303. child.keys[i + t] = sibling.keys[i];
304.
305. // Copying the child pointers from sibling to child
306. if (!child.leaf) {
307. for (int i = 0; i <= sibling.n; ++i)
308. child.children[i + t] = sibling.children[i];
309. }
310.
311. // Move all keys after idx in the current node one step before to fill
the gap created by moving keys[idx] to child
312. for (int i = idx + 1; i < n; ++i)
313. keys[i - 1] = keys[i];
314.
315. // Move the child pointers after (idx+1) in current node one step
before
316. for (int i = idx + 2; i <= n; ++i)
317. children[i - 1] = children[i];
318.
319. // Update key counts
320. child.n += sibling.n + 1;
321. n--;
322. }
323.
324. // For debugging: print node keys
325. void printNode() {
326. System.out.print("[");
327. for (int i = 0; i < n; i++) {
328. System.out.print(keys[i]);
329. if (i < n - 1) System.out.print(" ");
330. }
331. System.out.print("]");
332. }
333. }
334.
335. class BTree {
336. BTreeNode root;
337. int t; // Minimum degree
338.
339. BTree(int t) {
340. this.root = null;
341. this.t = t;
342. }
343.
344. // Traverse tree in sorted order
345. void traverse() {
346. if (root != null) root.traverse();
347. System.out.println();
348. }
349.
350. // Level order traversal (breadth-first) showing nodes per level
351. void levelOrder() {
352. if (root == null) {
353. System.out.println("(empty tree)");
354. return;
355. }
356.
357. Queue<BTreeNode> q = new LinkedList<>();
358. q.add(root);
359.
360. while (!q.isEmpty()) {
361. int levelSize = q.size();
362. for (int i = 0; i < levelSize; i++) {
363. BTreeNode node = q.poll();
364. node.printNode();
365. System.out.print(" ");
366. if (!node.leaf) {
367. for (int j = 0; j <= node.n; j++) {
368. if (node.children[j] != null)
369. q.add(node.children[j]);
370. }
371. }
372. }
373. System.out.println();
374. }
375. }
376.
377. // Search key k in this tree
378. void search(int k) {
379. if (root == null) {
380. System.out.println("Key " + k + " not found!");
381. return;
382. }
383. BTreeNode node = root.search(k);
384. if (node != null)
385. System.out.println("Key " + k + " found in the tree.");
386. else
387. System.out.println("Key " + k + " not found!");
388. }
389.
390. // Insert a key into the B-tree
391. void insert(int k) {
392. if (root == null) {
393. // Allocate root
394. root = new BTreeNode(t, true);
395. root.keys[0] = k;
396. root.n = 1;
397. } else {
398. // If root is full, tree grows in height
399. if (root.n == 2 * t - 1) {
400. BTreeNode s = new BTreeNode(t, false);
401.
402. // Make old root as child of new root
403. s.children[0] = root;
404.
405. // Split the old root and move one key to new root
406. s.splitChild(0, root);
407.
408. // New root has two children now. Decide which child will have
new key
409. int i = 0;
410. if (s.keys[0] < k) i++;
411. s.children[i].insertNonFull(k);
412.
413. // Change root
414. root = s;
415. } else {
416. root.insertNonFull(k);
417. }
418. }
419. }
420.
421. // Remove a key from this B-tree
422. void delete(int k) {
423. if (root == null) {
424. System.out.println("The tree is empty. Cannot delete " + k);
425. return;
426. }
427.
428. root.remove(k);
429.
430. // If the root node has 0 keys, make its first child as the new root
if it has a child,
431. // otherwise set root as null.
432. if (root.n == 0) {
433. if (root.leaf)
434. root = null;
435. else
436. root = root.children[0];
437. }
438. }
439. }
440.
441. public class BTreeMenu {
442. public static void main(String[] args) {
443. Scanner sc = new Scanner(System.in);
444. int degree;
445.
446. System.out.print("Enter minimum degree t for B-Tree (t >= 2
recommended): ");
447. while (true) {
448. try {
449. degree = sc.nextInt();
450. if (degree < 2) {
451. System.out.print("Please enter an integer >= 2: ");
452. continue;
453. }
454. break;
455. } catch (InputMismatchException e) {
456. sc.next(); // consume invalid
457. System.out.print("Please enter a valid integer: ");
458. }
459. }
460.
461. BTree tree = new BTree(degree);
462.
463. // Pre-load some sample keys for quick testing (optional)
464. System.out.print("Do you want sample keys inserted? (y/n): ");
465. char ans = sc.next().toLowerCase().charAt(0);
466. if (ans == 'y') {
467. int[] sample = {10, 20, 5, 6, 12, 30, 7, 17};
468. for (int k : sample) tree.insert(k);
469. System.out.println("Sample keys inserted: " +
Arrays.toString(sample));
470. }
471.
472. while (true) {
473. System.out.println("\n--- B-Tree Menu ---");
474. System.out.println("1. Insert key");
475. System.out.println("2. Search key");
476. System.out.println("3. Delete key");
477. System.out.println("4. Traverse (sorted order)");
478. System.out.println("5. Display Level Order (show nodes per
level)");
479. System.out.println("6. Exit");
480. System.out.print("Enter your choice: ");
481.
482. int choice;
483. try {
484. choice = sc.nextInt();
485. } catch (InputMismatchException e) {
486. sc.next(); // consume
487. System.out.println("Invalid input. Try again.");
488. continue;
489. }
490.
491. switch (choice) {
492. case 1:
493. System.out.print("Enter key to insert: ");
494. try {
495. int key = sc.nextInt();
496. tree.insert(key);
497. System.out.println("Inserted " + key);
498. } catch (InputMismatchException e) {
499. sc.next();
500. System.out.println("Invalid key.");
501. }
502. break;
503. case 2:
504. System.out.print("Enter key to search: ");
505. try {
506. int key = sc.nextInt();
507. tree.search(key);
508. } catch (InputMismatchException e) {
509. sc.next();
510. System.out.println("Invalid key.");
511. }
512. break;
513. case 3:
514. System.out.print("Enter key to delete: ");
515. try {
516. int key = sc.nextInt();
517. tree.delete(key);
518. } catch (InputMismatchException e) {
519. sc.next();
520. System.out.println("Invalid key.");
521. }
522. break;
523. case 4:
524. System.out.println("B-Tree in sorted order:");
525. tree.traverse();
526. break;
527. case 5:
528. System.out.println("B-Tree Level Order (each node shown as
[keys]):");
529. tree.levelOrder();
530. break;
531. case 6:
532. System.out.println("Exiting.");
533. sc.close();
534. System.exit(0);
535. default:
536. System.out.println("Invalid choice. Choose 1-6.");
537. }
538. }
539. }
540. }
 LAB PROGRAM - 5
1. Design and implement a menu-driven Java program to perform operations on a multi-way search
tree(B-Trees) suitable for indexing large amounts of data. The tree should allow multiple keys to be
stored in a single node and should maintain balance automatically during insertions and deletions by
redistributing or merging keys when required. The program should support inserting new keys,
deleting existing keys, and searching for a given key efficiently. It should also provide options to
traverse and display the contents of the tree in sorted order and in level-wise structure to visualize the
hierarchy. The implementation must ensure that the tree remains balanced after every update so that
search, insert, and delete operations can always be performed in logarithmic time. Proper messages
should be displayed for unsuccessful search or delete operations, and the program should be tested
with a set of sample keys to demonstrate how the structure grows and shrinks dynamically.

2. import java.util.*;
3.
4. // B-Tree Node
5. class BTreeNode {
6. int[] keys;
7. int t; // Minimum degree
8. BTreeNode[] children;
9. int n; // Current number of keys
10. boolean leaf;
11.
12. BTreeNode(int t, boolean leaf) {
13. this.t = t;
14. this.leaf = leaf;
15. this.keys = new int[2 * t - 1];
16. this.children = new BTreeNode[2 * t];
17. this.n = 0;
18. }
19.
20. void traverse() {
21. int i;
22. for (i = 0; i < n; i++) {
23. if (!leaf) children[i].traverse();
24. System.out.print(keys[i] + " ");
25. }
26. if (!leaf) children[i].traverse();
27. }
28.
29. BTreeNode search(int k) {
30. int i = 0;
31. while (i < n && k > keys[i]) i++;
32. if (i < n && keys[i] == k) return this;
33. if (leaf) return null;
34. return children[i].search(k);
35. }
36.
37. void insertNonFull(int k) {
38. int i = n - 1;
39. if (leaf) {
40. while (i >= 0 && keys[i] > k) {
41. keys[i + 1] = keys[i];
42. i--;
43. }
44. keys[i + 1] = k;
45. n++;
46. } else {
47. while (i >= 0 && keys[i] > k) i--;
48. i++;
49. if (children[i].n == 2 * t - 1) {
50. splitChild(i, children[i]);
51. if (keys[i] < k) i++;
52. }
53. children[i].insertNonFull(k);
54. }
55. }
56.
57. void splitChild(int i, BTreeNode y) {
58. BTreeNode z = new BTreeNode(y.t, y.leaf);
59. z.n = t - 1;
60. for (int j = 0; j < t - 1; j++) z.keys[j] = y.keys[j + t];
61. if (!y.leaf)
62. for (int j = 0; j < t; j++) z.children[j] = y.children[j + t];
63. y.n = t - 1;
64. for (int j = n; j >= i + 1; j--) children[j + 1] = children[j];
65. children[i + 1] = z;
66. for (int j = n - 1; j >= i; j--) keys[j + 1] = keys[j];
67. keys[i] = y.keys[t - 1];
68. n++;
69. }
70.
71. // Delete a key k from subtree rooted at this node
72. void remove(int k) {
73. int idx = findKey(k);
74.
75. if (idx < n && keys[idx] == k) {
76. if (leaf) removeFromLeaf(idx);
77. else removeFromNonLeaf(idx);
78. } else {
79. if (leaf) {
80. System.out.println("Key " + k + " not found.");
81. return;
82. }
83.
84. boolean flag = (idx == n);
85.
86. if (children[idx].n < t)
87. fill(idx);
88.
89. if (flag && idx > n)
90. children[idx - 1].remove(k);
91. else
92. children[idx].remove(k);
93. }
94. }
95.
96. int findKey(int k) {
97. int idx = 0;
98. while (idx < n && keys[idx] < k) ++idx;
99. return idx;
100. }
101.
102. void removeFromLeaf(int idx) {
103. for (int i = idx + 1; i < n; ++i)
104. keys[i - 1] = keys[i];
105. n--;
106. System.out.println("Key deleted.");
107. }
108.
109. void removeFromNonLeaf(int idx) {
110. int k = keys[idx];
111.
112. if (children[idx].n >= t) {
113. int pred = getPredecessor(idx);
114. keys[idx] = pred;
115. children[idx].remove(pred);
116. } else if (children[idx + 1].n >= t) {
117. int succ = getSuccessor(idx);
118. keys[idx] = succ;
119. children[idx + 1].remove(succ);
120. } else {
121. merge(idx);
122. children[idx].remove(k);
123. }
124. }
125.
126. int getPredecessor(int idx) {
127. BTreeNode cur = children[idx];
128. while (!cur.leaf) cur = cur.children[cur.n];
129. return cur.keys[cur.n - 1];
130. }
131.
132. int getSuccessor(int idx) {
133. BTreeNode cur = children[idx + 1];
134. while (!cur.leaf) cur = cur.children[0];
135. return cur.keys[0];
136. }
137.
138. void fill(int idx) {
139. if (idx != 0 && children[idx - 1].n >= t)
140. borrowFromPrev(idx);
141. else if (idx != n && children[idx + 1].n >= t)
142. borrowFromNext(idx);
143. else {
144. if (idx != n) merge(idx);
145. else merge(idx - 1);
146. }
147. }
148.
149. void borrowFromPrev(int idx) {
150. BTreeNode child = children[idx];
151. BTreeNode sibling = children[idx - 1];
152.
153. for (int i = child.n - 1; i >= 0; --i) child.keys[i + 1] =
child.keys[i];
154. if (!child.leaf) {
155. for (int i = child.n; i >= 0; --i) child.children[i + 1] =
child.children[i];
156. }
157.
158. child.keys[0] = keys[idx - 1];
159. if (!child.leaf) child.children[0] = sibling.children[sibling.n];
160.
161. keys[idx - 1] = sibling.keys[sibling.n - 1];
162.
163. child.n += 1;
164. sibling.n -= 1;
165. }
166.
167. void borrowFromNext(int idx) {
168. BTreeNode child = children[idx];
169. BTreeNode sibling = children[idx + 1];
170.
171. child.keys[child.n] = keys[idx];
172.
173. if (!child.leaf) child.children[child.n + 1] = sibling.children[0];
174.
175. keys[idx] = sibling.keys[0];
176.
177. for (int i = 1; i < sibling.n; ++i) sibling.keys[i - 1] =
sibling.keys[i];
178.
179. if (!sibling.leaf) {
180. for (int i = 1; i <= sibling.n; ++i) sibling.children[i - 1] =
sibling.children[i];
181. }
182.
183. child.n += 1;
184. sibling.n -= 1;
185. }
186.
187. void merge(int idx) {
188. BTreeNode child = children[idx];
189. BTreeNode sibling = children[idx + 1];
190.
191. child.keys[t - 1] = keys[idx];
192.
193. for (int i = 0; i < sibling.n; ++i) child.keys[i + t] =
sibling.keys[i];
194.
195. if (!child.leaf)
196. for (int i = 0; i <= sibling.n; ++i) child.children[i + t] =
sibling.children[i];
197.
198. for (int i = idx + 1; i < n; ++i) keys[i - 1] = keys[i];
199. for (int i = idx + 2; i <= n; ++i) children[i - 1] = children[i];
200.
201. child.n += sibling.n + 1;
202. n--;
203. }
204.
205. void printNode() {
206. System.out.print("[");
207. for (int i = 0; i < n; i++) {
208. System.out.print(keys[i]);
209. if (i < n - 1) System.out.print(" ");
210. }
211. System.out.print("]");
212. }
213. }
214.
215. // B-Tree
216. class BTree {
217. BTreeNode root;
218. int t;
219.
220. BTree(int t) { this.t = t; root = null; }
221.
222. void traverse() {
223. if (root != null) root.traverse();
224. System.out.println();
225. }
226.
227. void levelOrder() {
228. if (root == null) { System.out.println("(empty tree)"); return; }
229. Queue<BTreeNode> q = new LinkedList<>();
230. q.add(root);
231. while (!q.isEmpty()) {
232. int levelSize = q.size();
233. for (int i = 0; i < levelSize; i++) {
234. BTreeNode node = q.poll();
235. node.printNode();
236. System.out.print(" ");
237. if (!node.leaf)
238. for (int j = 0; j <= node.n; j++)
239. if (node.children[j] != null) q.add(node.children[j]);
240. }
241. System.out.println();
242. }
243. }
244.
245. void insert(int k) {
246. if (root == null) {
247. root = new BTreeNode(t, true);
248. root.keys[0] = k; root.n = 1;
249. } else {
250. if (root.n == 2 * t - 1) {
251. BTreeNode s = new BTreeNode(t, false);
252. s.children[0] = root;
253. s.splitChild(0, root);
254. int i = (s.keys[0] < k) ? 1 : 0;
255. s.children[i].insertNonFull(k);
256. root = s;
257. } else root.insertNonFull(k);
258. }
259. }
260.
261. void search(int k) {
262. if (root == null) System.out.println("Key " + k + " not found");
263. else if (root.search(k) != null) System.out.println("Key " + k + "
found");
264. else System.out.println("Key " + k + " not found");
265. }
266.
267. void delete(int k) {
268. if (root == null) { System.out.println("Tree empty"); return; }
269. root.remove(k);
270. if (root.n == 0) {
271. if (root.leaf) root = null;
272. else root = root.children[0];
273. }
274. }
275. }
276.
277. // Menu-driven program
278. public class Program2 {
279. public static void main(String[] args) {
280. Scanner sc = new Scanner(System.in);
281. BTree tree = new BTree(3);
282.
283. // Sample keys
284. int[] sample = {10, 20, 5, 6, 12, 30, 7, 17};
285. for (int k : sample) tree.insert(k);
286. System.out.println("Sample keys inserted: " +
Arrays.toString(sample));
287.
288. while (true) {
289. System.out.println("\n--- B-Tree Menu ---");
290. System.out.println("1. Insert key");
291. System.out.println("2. Search key");
292. System.out.println("3. Delete key");
293. System.out.println("4. Traverse (sorted)");
294. System.out.println("5. Level Order");
295. System.out.println("6. Exit");
296.
297. if (!sc.hasNextInt()) { sc.next(); System.out.println("Invalid
input"); continue; }
298. int choice = sc.nextInt();
299.
300. switch (choice) {
301. case 1:
302. System.out.print("Enter key: ");
303. if (sc.hasNextInt()) tree.insert(sc.nextInt());
304. else { System.out.println("Invalid key"); sc.next(); }
305. break;
306. case 2:
307. System.out.print("Enter key: ");
308. if (sc.hasNextInt()) tree.search(sc.nextInt());
309. else { System.out.println("Invalid key"); sc.next(); }
310. break;
311. case 3:
312. System.out.print("Enter key: ");
313. if (sc.hasNextInt()) tree.delete(sc.nextInt());
314. else { System.out.println("Invalid key"); sc.next(); }
315. break;
316. case 4: tree.traverse(); break;
317. case 5: tree.levelOrder(); break;
318. case 6: System.out.println("Exiting."); return;
319. default: System.out.println("Invalid choice");
320. }
321. }
322. }
323. }
324.
2. Design and implement a menu-driven Java program to construct and manipulate a binary heap for a
dynamic set of elements. The program should allow the user to insert new elements while maintaining
the heap property, delete elements such as the root (maximum in a max-heap or minimum in a min-
heap), and efficiently retrieve the highest or lowest priority element depending on the chosen heap
type. It should also provide functionality to build a heap from an unsorted array, display the elements
in heap order, and perform a heap sort to arrange the data in ascending or descending order.

3. import java.util.*;
4.
5. class BinaryHeap {
6. private ArrayList<Integer> heap;
7. private boolean isMaxHeap;
8.
9. public BinaryHeap(boolean isMaxHeap) {
10. this.heap = new ArrayList<>();
11. this.isMaxHeap = isMaxHeap;
12. }
13.
14. private boolean compare(int a, int b) {
15. return isMaxHeap ? a > b : a < b;
16. }
17.
18. private void swap(int i, int j) {
19. int tmp = heap.get(i);
20. heap.set(i, heap.get(j));
21. heap.set(j, tmp);
22. }
23.
24. public void insert(int key) {
25. heap.add(key);
26. int i = heap.size() - 1;
27.
28. while (i > 0) {
29. int parent = (i - 1) / 2;
30. if (compare(heap.get(i), heap.get(parent))) {
31. swap(i, parent);
32. i = parent;
33. } else break;
34. }
35. }
36.
37. public int getRoot() {
38. if (heap.isEmpty()) throw new NoSuchElementException("Heap is empty");
39. return heap.get(0);
40. }
41.
42. public int deleteRoot() {
43. if (heap.isEmpty()) throw new NoSuchElementException("Heap is empty");
44. int root = heap.get(0);
45. int last = heap.remove(heap.size() - 1);
46. if (!heap.isEmpty()) {
47. heap.set(0, last);
48. heapify(0);
49. }
50. return root;
51. }
52.
53. private void heapify(int i) {
54. int size = heap.size();
55. int left = 2 * i + 1;
56. int right = 2 * i + 2;
57. int extreme = i;
58.
59. if (left < size && compare(heap.get(left), heap.get(extreme))) extreme =
left;
60. if (right < size && compare(heap.get(right), heap.get(extreme))) extreme
= right;
61.
62. if (extreme != i) {
63. swap(i, extreme);
64. heapify(extreme);
65. }
66. }
67.
68. public void buildHeap(int[] arr) {
69. heap.clear();
70. for (int num : arr) heap.add(num);
71. for (int i = (heap.size() - 2) / 2; i >= 0; i--) heapify(i);
72. }
73.
74. public void displayHeap() {
75. System.out.println("Heap array: " + heap);
76. }
77.
78. // Level-order display to visualize tree
79. public void displayLevelOrder() {
80. int n = heap.size();
81. int level = 0, count = 0, nextLevel = 1;
82. System.out.println("Heap level-wise:");
83. for (int i = 0; i < n; i++) {
84. System.out.print(heap.get(i) + " ");
85. count++;
86. if (count == nextLevel) {
87. System.out.println();
88. level++;
89. nextLevel = (int) Math.pow(2, level);
90. count = 0;
91. }
92. }
93. if (count > 0) System.out.println();
94. }
95.
96. public void heapSort() {
97. ArrayList<Integer> copy = new ArrayList<>(heap);
98. ArrayList<Integer> sorted = new ArrayList<>();
99. while (!heap.isEmpty()) sorted.add(deleteRoot());
100. if (isMaxHeap) Collections.reverse(sorted); // max-heap -> descending
101. System.out.println("Heap sorted: " + sorted);
102. heap = copy; // restore original heap
103. }
104. }
105.
106. public class HeapMenu {
107. public static void main(String[] args) {
108. Scanner sc = new Scanner(System.in);
109.
110. System.out.println("Choose Heap Type: 1. Max-Heap 2. Min-Heap");
111. int type = sc.nextInt();
112. boolean isMaxHeap = (type == 1);
113.
114. BinaryHeap heap = new BinaryHeap(isMaxHeap);
115.
116. while (true) {
117. System.out.println("\n--- Heap Menu ---");
118. System.out.println("1. Insert element");
119. System.out.println("2. Delete root element");
120. System.out.println("3. Get root element");
121. System.out.println("4. Build heap from array");
122. System.out.println("5. Display heap array");
123. System.out.println("6. Display heap level-wise");
124. System.out.println("7. Heap sort");
125. System.out.println("8. Exit");
126.
127. int choice = sc.nextInt();
128.
129. switch (choice) {
130. case 1:
131. System.out.print("Enter element to insert: ");
132. heap.insert(sc.nextInt());
133. break;
134. case 2:
135. try {
136. int removed = heap.deleteRoot();
137. System.out.println("Deleted root: " + removed);
138. } catch (NoSuchElementException e) {
139. System.out.println("Heap is empty");
140. }
141. break;
142. case 3:
143. try {
144. System.out.println("Root element: " + heap.getRoot());
145. } catch (NoSuchElementException e) {
146. System.out.println("Heap is empty");
147. }
148. break;
149. case 4:
150. System.out.print("Enter number of elements: ");
151. int n = sc.nextInt();
152. int[] arr = new int[n];
153. System.out.println("Enter elements:");
154. for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
155. heap.buildHeap(arr);
156. break;
157. case 5:
158. heap.displayHeap();
159. break;
160. case 6:
161. heap.displayLevelOrder();
162. break;
163. case 7:
164. heap.heapSort();
165. break;
166. case 8:
167. System.out.println("Exiting...");
168. return;
169. default:
170. System.out.println("Invalid choice");
171. }
172. }
173. }
174. }
175.