Advanced Data Structures Lab Programs int gp = parent(parent(i));

if ((gp >= 0) && (h->heap[gp] > h->heap[i])) {

swap(&h->heap[gp], &h->heap[i]);
Lab – 04 bubble_Up_Max(h, gp);
Write a program to perform the following operations: }
}
a) Insert an element into a Min-Max heap void bubble_Up(MinMaxHeap *h, int i) {
b) Delete an element from a Min-Max heap if (i == 0) return;
c) Search for a key element in a Min-Max heap int p = parent(i);
int lvl = level(i);
if (lvl % 2 == 0) { // even level → MIN level
if (h->heap[p] < h->heap[i]) {
In C Language : swap(&h->heap[p], &h->heap[i]);
#include <stdio.h> bubble_Up(h, p);
#include <stdlib.h> } else {
#include <math.h> bubble_Up_Max(h, i);
#include <limits.h> }
#define MAX_SIZE 100 } else { // odd level → MAX level
typedef struct { if (h->heap[p] > h->heap[i]) {
int heap[MAX_SIZE]; swap(&h->heap[p], &h->heap[i]);
int size; bubble_Up(h, p);
} MinMaxHeap; } else {
void initialize_heap(MinMaxHeap *h) { bubble_Up_Min(h, i);
h->size = 0; }
} }
int parent(int i) { return (i - 1) / 2; } }
int left_child(int i) { return 2 * i + 1; } void insert(MinMaxHeap *h, int value) {
int right_child(int i) { return 2 * i + 2; } if (h->size == MAX_SIZE) return;
int level(int i) { return (int)log2(i + 1); } h->heap[h->size] = value;
void swap(int *a, int *b) { bubble_Up(h, h->size);
int temp = *a; h->size++;
*a = *b; }
*b = temp; void display(MinMaxHeap *h) {
} printf("Heap = [");
void bubble_Up_Min(MinMaxHeap *h, int i) { for (int i = 0; i < h->size; i++) {
int gp = parent(parent(i)); printf("%d", h->heap[i]);
if ((gp >= 0) && (h->heap[gp] < h->heap[i])) { if (i < h->size - 1) printf(", ");
swap(&h->heap[gp], &h->heap[i]); }
bubble_Up_Min(h, gp); printf("]\n");
} }
} int find_Smallest_Desendand(MinMaxHeap *h, int i) {
void bubble_Up_Max(MinMaxHeap *h, int i) { int candidates[6] = {
 left_child(i), right_child(i), }
void bubble_Down_Min(MinMaxHeap *h, int i) {
left_child(left_child(i)), right_child(left_child(i)), int m = find_Smallest_Desendand(h, i);
if (m == -1) return;
left_child(right_child(i)), right_child(right_child(i)) if (h->heap[m] < h->heap[i]) {
}; swap(&h->heap[m], &h->heap[i]);
int minVal = INT_MAX, minIdx = -1; int p = parent(m);
for (int j = 0; j < 6; j++) { if (p >= 0 && h->heap[m] > h->heap[p]) swap(&h-
int idx = candidates[j]; >heap[m], &h->heap[p]);
if (idx < h->size && h->heap[idx] < minVal) { bubble_Down_Min(h, m);
minVal = h->heap[idx]; }
minIdx = idx; }
} void bubble_Down_Max(MinMaxHeap *h, int i) {
} int m = find_Largest_Desendand(h, i);
return minIdx; if (m == -1) return;
} if (h->heap[m] > h->heap[i]) {
int find_Largest_Desendand(MinMaxHeap *h, int i) { swap(&h->heap[m], &h->heap[i]);
int candidates[6] = { int p = parent(m);
left_child(i), right_child(i), if (p >= 0 && h->heap[m] < h->heap[p]) swap(&h-
>heap[m], &h->heap[p]);
left_child(left_child(i)), right_child(left_child(i)), bubble_Down_Max(h, m);
}
left_child(right_child(i)), right_child(right_child(i)) }
}; int delete_Min(MinMaxHeap *h) {
int maxVal = INT_MIN, maxIdx = -1; if (h->size == 0) return INT_MIN;
for (int j = 0; j < 6; j++) { int minVal = h->heap[0];
int idx = candidates[j]; h->heap[0] = h->heap[h->size - 1];
if (idx < h->size && h->heap[idx] > maxVal) { h->size--;
maxVal = h->heap[idx]; if (h->size > 0) bubble_Down(h, 0);
maxIdx = idx; return minVal;
} }
} int delete_Max(MinMaxHeap *h) {
return maxIdx; if (h->size == 0) return INT_MAX;
} if (h->size == 1) {
void bubble_Down_Min(MinMaxHeap *h, int i); int val = h->heap[0];
void bubble_Down_Max(MinMaxHeap *h, int i); h->size--;
void bubble_Down(MinMaxHeap *h, int i) { return val;
int lvl = level(i); }
if (lvl % 2 == 0) int maxIdx = (h->size == 2 || h->heap[1] > h-
bubble_Down_Min(h, i); >heap[2]) ? 1 : 2;
else int maxVal = h->heap[maxIdx];
bubble_Down_Max(h, i); h->heap[maxIdx] = h->heap[h->size - 1];
 h->size--; scanf("%d", &key);
if (h->size > maxIdx) bubble_Down(h, maxIdx); insert(&h, key);
return maxVal; display(&h);
} break;
int getMin(MinMaxHeap *h) { case 2:
return (h->size > 0) ? h->heap[0] : INT_MIN; printf("Minimum element: %d\
} n", getMin(&h));
int getMax(MinMaxHeap *h) { break;
if (h->size == 0) return INT_MIN; case 3:
if (h->size == 1) return h->heap[0]; printf("Maximum element: %d\
if (h->size == 2) return h->heap[1]; n", getMax(&h));
return (h->heap[1] > h->heap[2]) ? h->heap[1] : h- break;
>heap[2]; case 4:
} printf("Deleted Minimum: %d\
void search(MinMaxHeap *h, int key) { n", delete_Min(&h));
for (int i = 0; i < h->size; i++) { display(&h);
if (h->heap[i] == key) { break;
printf("Element found at index: %d\n", i); case 5:
return; printf("Deleted Maximum: %d\
} n", delete_Max(&h));
} display(&h);
printf("Element was not found\n"); break;
} case 6:
int main() { printf("Enter element to search: ");
MinMaxHeap h; scanf("%d", &key);
initialize_heap(&h); search(&h, key);
int choice, key, flag = 1; break;
while (flag) { case 7:
printf("\n\nChoose the Operation:\n"); display(&h);
printf("1. Insertion\n"); break;
printf("2. Get Minimum\n"); case 0:
printf("3. Get Maximum\n"); flag = 0;
printf("4. Delete Minimum\n"); printf("Exiting...\n");
printf("5. Delete Maximum\n"); break;
printf("6. Search\n"); default:
printf("7. Display\n"); printf("Invalid choice. Try again.\n");
printf("0. Exit\n"); }
printf("Enter your choice: "); }
scanf("%d", &choice);
switch (choice) { return 0;
case 1: }
printf("Enter element to insert: ");
 return 2 * i + 1
def right(self, i):
"""Return right child index of node i."""
In Python Language : return 2 * i + 2
def level(self, i):
"""
"""Return level (depth) of index i in the
---------------------------------------------------------
heap."""
Min-Max Heap Implementation in Python
return int(math.log2(i + 1))
---------------------------------------------------------
def swap(self, i, j):
A Min-Max Heap is a complete binary tree that allows:
"""Swap two elements in the heap."""
- O(1) access to both the minimum and maximum elements.
[Link][i], [Link][j]
- O(log n) insertion and deletion.
= [Link][j], [Link][i]
This implementation supports:
@property
1. insert(value)
def size(self):
2. get_min()
"""Return current heap size."""
3. get_max()
return len([Link])
4. delete_min()
# ---------------------------------------------------
5. delete_max()
# Bubble-up operations (restore heap after insertion)
6. search(value)
# ---------------------------------------------------
7. display()
def bubble_up_min(self, i):
Author : Pravalika Srinivas
"""Bubble up on even (min) levels."""
Language : Python
grandparent
---------------------------------------------------------
= [Link]([Link](i)) if [Link](i) is not Non
"""
e else None
import math
if grandparent is not None and [Link][i]
< [Link][grandparent]:
class MinMaxHeap: [Link](i, grandparent)
"""Class implementing a Min-Max Heap data self.bubble_up_min(grandparent)
structure.""" def bubble_up_max(self, i):
def __init__(self, capacity=100): """Bubble up on odd (max) levels."""
"""Initialize an empty heap with a given grandparent
capacity.""" = [Link]([Link](i)) if [Link](i) is not Non
[Link] = [] e else None
[Link] = capacity if grandparent is not None and [Link][i]
# --------------------------------------------------- > [Link][grandparent]:
# Helper functions for index and structure management [Link](i, grandparent)
# --------------------------------------------------- self.bubble_up_max(grandparent)
def parent(self, i): def bubble_up(self, i):
"""Return parent index of node i.""" """Restore heap property after insertion."""
return (i - 1) // 2 if i > 0 else None if i == 0:
def left(self, i): return
"""Return left child index of node i.""" p = [Link](i)
 if p is None: ]
return indices = [idx for idx in indices if idx
if [Link](i) % 2 == 0: # even = min level < [Link]]
if [Link][i] > [Link][p]: if not indices:
[Link](i, p) return -1
self.bubble_up_max(p) return max(indices, key=lambda x: [Link][x])
else: def _trickle_down_min(self, i):
self.bubble_up_min(i) """Restore heap property when current level is
else: # odd = max level min."""
if [Link][i] < [Link][p]: m = self._find_smallest_descendant(i)
[Link](i, p) if m == -1:
self.bubble_up_min(p) return
else: if [Link](m) >= [Link](i) + 2: #
self.bubble_up_max(i) grandchild
# --------------------------------------------------- if [Link][m] < [Link][i]:
# Trickle-down operations (restore heap after [Link](m, i)
deletion) p = [Link](m)
# --------------------------------------------------- if [Link][m] > [Link][p]:
def _find_smallest_descendant(self, i): [Link](m, p)
"""Find the index of the smallest descendant self._trickle_down_min(m)
(child/grandchild).""" else: # child
indices = [ if [Link][m] < [Link][i]:
[Link](i), [Link](i), [Link](m, i)
def _trickle_down_max(self, i):
[Link]([Link](i)), [Link]([Link](i)), """Restore heap property when current level is
max."""
[Link]([Link](i)), [Link]([Link](i)) m = self._find_largest_descendant(i)
] if m == -1:
indices = [idx for idx in indices if idx return
< [Link]] if [Link](m) >= [Link](i) + 2: #
if not indices: grandchild
return -1 if [Link][m] > [Link][i]:
return min(indices, key=lambda x: [Link][x]) [Link](m, i)
def _find_largest_descendant(self, i): p = [Link](m)
"""Find the index of the largest descendant if [Link][m] < [Link][p]:
(child/grandchild).""" [Link](m, p)
indices = [ self._trickle_down_max(m)
[Link](i), [Link](i), else: # child
if [Link][m] > [Link][i]:
[Link]([Link](i)), [Link]([Link](i)), [Link](m, i)
def trickle_down(self, i):
[Link]([Link](i)), [Link]([Link](i))
 """Wrapper to call appropriate trickle-down if n == 0:
function.""" return None
if [Link](i) % 2 == 0: elif n == 1:
self._trickle_down_min(i) return [Link]()
else: elif n == 2:
self._trickle_down_max(i) return [Link](1)
# --------------------------------------------------- # Determine which child (1 or 2) has max value
# Core Heap Operations max_index = 1 if [Link][1]
# --------------------------------------------------- > [Link][2] else 2
def insert(self, value): max_val = [Link][max_index]
"""Insert a new value into the heap.""" last = [Link]()
if [Link] >= [Link]: if max_index < len([Link]):
print("Heap is full!") [Link][max_index] = last
return self._trickle_down_max(max_index)
[Link](value) return max_val
self.bubble_up([Link] - 1) def search(self, value):
def get_min(self): """Search for a value in the heap."""
"""Return the minimum element in O(1).""" if value in [Link]:
return [Link][0] if [Link] > 0 else None print(f" {value} found at
def get_max(self): index {[Link](value)}")
"""Return the maximum element in O(1).""" else:
if [Link] == 0: print(f" {value} not found in heap.")
return None def display(self):
elif [Link] == 1: """Display the heap as a list."""
return [Link][0] print("Heap =", [Link])
elif [Link] == 2:
return [Link][1] # ---------------------------------------------------
else: # Interactive Menu for Testing
return max([Link][1], [Link][2]) # ---------------------------------------------------
def delete_min(self): if __name__ == "__main__":
"""Delete and return the minimum element.""" heap = MinMaxHeap()
if [Link] == 0: while True:
return None print("\n--- Min-Max Heap Menu ---")
min_val = [Link][0] print("1. Insert")
last = [Link]() print("2. Get Minimum")
if [Link] > 0: print("3. Get Maximum")
[Link][0] = last print("4. Delete Minimum")
self._trickle_down_min(0) print("5. Delete Maximum")
return min_val print("6. Search")
def delete_max(self): print("7. Display")
"""Delete and return the maximum element.""" print("0. Exit")
n = [Link] choice = input("Enter your choice: ")
if choice == "1":
val = int(input("Enter value to insert: "))
[Link](val)
[Link]()
elif choice == "2":
print("Minimum:", heap.get_min())
elif choice == "3":
print("Maximum:", heap.get_max())
elif choice == "4":
print("Deleted Minimum:", heap.delete_min())
[Link]()
elif choice == "5":
print("Deleted Maximum:", heap.delete_max())
[Link]()
elif choice == "6":
val = int(input("Enter value to search: "))
[Link](val)
elif choice == "7":
[Link]()
elif choice == "0":
print("Exiting...")
break
else:
print("Invalid choice. Please try again.")
 if (L == NULL || R == NULL) {
printf("Memory allocation failed!\n");
return;
}

// Copy data to temp arrays

for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

// Merge the temp arrays back into arr[left..right]

int i = 0; // Starting index of left sub-array
int j = 0; // Starting index of right sub-array
int k = left; // Starting index of merged sub-array

Lab – 02 while (i < n1 && j < n2) {

if (L[i] <= R[j]) {
Write a program for implementing the following sorting arr[k] = L[i];
methods: i++;
} else {
a) Merge sort b) Heap sort c) Quick sort arr[k] = R[j];
Merge Sort j++;
}
In C Language : k++;
}
// Merge Sort Algorithm in C
// Documentation: Merge sort divides the array into // Copy remaining elements of L[] if any
halves, sorts them recursively, and merges sorted halves. while (i < n1) {
// Time Complexity: O(n log n) | Space: O(n) arr[k] = L[i];
#include <stdio.h> i++;
#include <stdlib.h> k++;
// Merge function documentation: Merges two sorted halves }
[left...mid] and [mid+1...right]
void merge(int arr[], int left, int mid, int right) { // Copy remaining elements of R[] if any
// Calculate sizes of two sub-arrays while (j < n2) {
int n1 = mid - left + 1; arr[k] = R[j];
int n2 = right - mid; j++;
k++;
// Create temp arrays }
int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int)); // Free temp arrays
 free(L);
free(R); printf("Original array: ");
} printArray(arr, n);
// MergeSort function documentation: Recursively sorts
using divide and conquer mergesort(arr, 0, n - 1);
void mergesort(int arr[], int left, int right) {
if (left < right) { printf("Sorted array: ");
int mid = left + (right - left) / 2; // Avoid printArray(arr, n);
overflow
free(arr); // Free memory
// Sort first half return 0;
mergesort(arr, left, mid); }

// Sort second half

mergesort(arr, mid + 1, right);
C:\Advanced Data Structures Lab\Lab-02>merge_sort.exe
// Merge the sorted halves
Enter the number of elements: 4
merge(arr, left, mid, right);
} Enter 4 elements: 1
} 34
// Print array function 23
void printArray(int arr[], int size) { 12
for (int i = 0; i < size; i++)
Original array: 1 34 23 12
printf("%d ", arr[i]);
printf("\n"); Sorted array: 1 12 23 34
}
// Main - User input
int main() {
int n; In Python :
printf("Enter the number of elements: ");
# Merge Sort Algorithm in Python
scanf("%d", &n);
# Documentation: Merge sort divides the array into halves,
sorts them recursively, and merges sorted halves.
int *arr = (int*)malloc(n * sizeof(int));
# Time Complexity: O(n log n) | Space: O(n)
if (arr == NULL) {
def merge(arr, left, mid, right):
printf("Memory allocation failed!\n");
"""
return 1;
Merges two sorted halves of the array [left...mid] and
}
[mid+1...right].
Documentation: Creates temp arrays, compares and
printf("Enter %d elements: ", n);
merges elements in sorted order.
for (int i = 0; i < n; i++) {
"""
scanf("%d", &arr[i]);
# Calculate sizes
}
n1 = mid - left + 1
 n2 = right - mid """
if left < right:
# Create temp arrays mid = left + (right - left) // 2 # Avoid
L = [0] * n1 overflow
R = [0] * n2
# Sort first half
# Copy data to temp arrays mergesort(arr, left, mid)
for i in range(n1):
L[i] = arr[left + i] # Sort second half
for j in range(n2): mergesort(arr, mid + 1, right)
R[j] = arr[mid + 1 + j]
# Merge the sorted halves
# Merge the temp arrays back into arr[left..right] merge(arr, left, mid, right)
i = 0 # Starting index of left sub-array # Main part - User input
j = 0 # Starting index of right sub-array if __name__ == "__main__":
k = left # Starting index of merged sub-array n = int(input("Enter the number of elements: "))
arr = []
while i < n1 and j < n2: print(f"Enter {n} elements: ")
if L[i] <= R[j]: for _ in range(n):
arr[k] = L[i] [Link](int(input()))
i += 1
else: print("Original array:", arr)
arr[k] = R[j]
j += 1 mergesort(arr, 0, len(arr) - 1)
k += 1
print("Sorted array:", arr)
# Copy remaining elements of L[] if any
while i < n1:
arr[k] = L[i] C:\Advanced Data Structures Lab\Lab-02>python merge_sort.py
i += 1 Enter the number of elements: 4
k += 1
Enter 4 elements:
# Copy remaining elements of R[] if any 1
while j < n2: 23
arr[k] = R[j] 12
j += 1 15
k += 1
def mergesort(arr, left, right):
Original array: [1, 23, 12, 15]
""" Sorted array: [1, 12, 15, 23]
Recursively sorts the array using divide and conquer.
Documentation: Base case: if left < right, find mid,
sort left half, sort right half, then merge.
 largest = right;

// If largest is not root

if (largest != i) {
// Swap
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

// Recursively heapify the affected subtree

heapify(arr, n, largest);
}
}
// HeapSort function documentation: First builds max heap,
then extracts elements one by one
void heapsort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
Heap Sort
// One by one extract elements
In C Language : for (int i = n - 1; i > 0; i--) {
// Move current root to end
// Heap Sort Algorithm in C int temp = arr[0];
// Documentation: Builds a max heap from the array, then arr[0] = arr[i];
repeatedly extracts the maximum element and heapifies the arr[i] = temp;
reduced heap.
// Time Complexity: O(n log n) | Space: O(1) - in-place // Call heapify on the reduced heap
#include <stdio.h> heapify(arr, i, 0);
#include <stdlib.h> }
// Heapify function documentation: Ensures the subtree }
rooted at index i satisfies the max heap property // Print array function
void heapify(int arr[], int n, int i) { void printArray(int arr[], int size) {
int largest = i; // Initialize largest as root for (int i = 0; i < size; i++)
int left = 2 * i + 1; printf("%d ", arr[i]);
int right = 2 * i + 2; printf("\n");
}
// See if left child is larger than root // Main - User input
if (left < n && arr[left] > arr[largest]) int main() {
largest = left; int n;
printf("Enter the number of elements: ");
// See if right child is larger than largest so far scanf("%d", &n);
if (right < n && arr[right] > arr[largest])
 # Documentation: Builds a max heap from the array, then
int *arr = (int*)malloc(n * sizeof(int)); repeatedly extracts the maximum element and heapifies the
if (arr == NULL) { reduced heap.
printf("Memory allocation failed!\n"); # Time Complexity: O(n log n) | Space: O(1) - in-place
return 1; def heapify(arr, n, i):
} """
Heapify function for max heap.
printf("Enter %d elements: ", n); Documentation: Ensures the subtree rooted at index i
for (int i = 0; i < n; i++) { satisfies the max heap property.
scanf("%d", &arr[i]); Compares parent with its children and swaps with the
} largest if necessary, then recurses.
"""
printf("Original array: "); largest = i # Initialize largest as root
printArray(arr, n); left = 2 * i + 1
right = 2 * i + 2
heapsort(arr, n);
# See if left child is larger than root
printf("Sorted array: "); if left < n and arr[left] > arr[largest]:
printArray(arr, n); largest = left

free(arr); // Free memory # See if right child is larger than largest so far
return 0; if right < n and arr[right] > arr[largest]:
} largest = right

# If largest is not root

if largest != i:
C:\Advanced Data Structures Lab\Lab-02>heap_Sort.exe # Swap
Enter the number of elements: 4 arr[i], arr[largest] = arr[largest], arr[i]
# Recursively heapify the affected subtree
Enter 4 elements: 1 heapify(arr, n, largest)
22 def heapsort(arr):
32 """
12 Main heap sort function.
Original array: 1 22 32 12 Documentation: First builds max heap, then for each
element from end to start: swaps root with end, reduces
Sorted array: 1 12 22 32 heap size, and heapifies root.
"""
n = len(arr)
In Python Language : # Build max heap
# Heap Sort Algorithm in Python for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
 # One by one extract elements
for i in range(n - 1, 0, -1):
# Move current root to end
arr[0], arr[i] = arr[i], arr[0]
# Call heapify on the reduced heap
heapify(arr, i, 0)
# Main part - User input
if __name__ == "__main__":
n = int(input("Enter the number of elements: "))
arr = []
print(f"Enter {n} elements: ")
for _ in range(n):
[Link](int(input()))

print("Original array:", arr)

heapsort(arr)

print("Sorted array:", arr) Quick Sort

In C Language:
C:\Advanced Data Structures Lab\Lab-02>python heap_sort.py // Quick Sort Algorithm in C
Enter the number of elements: 6 // Documentation: Selects a pivot, partitions the array
Enter 6 elements: around it (smaller elements left, larger right), and
1 recursively sorts sub-arrays.
45 // Time Complexity: Average O(n log n), Worst O(n²) |
Space: O(log n) - recursive calls
23
#include <stdio.h>
12 #include <stdlib.h>
2 // Partition function documentation: Uses last element as
33 pivot. Rearranges array so elements <= pivot left, >
Original array: [1, 45, 23, 12, 2, 33] right
int partition(int arr[], int low, int high) {
Sorted array: [1, 2, 12, 23, 33, 45]
int pivot = arr[high]; // Choose last element as
pivot
int i = low - 1; // Index of smaller element

for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
 int temp = arr[i]; }
arr[i] = arr[j];
arr[j] = temp; printf("Enter %d elements: ", n);
} for (int i = 0; i < n; i++) {
} scanf("%d", &arr[i]);
}
// Swap pivot with i+1
int temp = arr[i + 1]; printf("Original array: ");
arr[i + 1] = arr[high]; printArray(arr, n);
arr[high] = temp;
quicksort(arr, 0, n - 1);
return i + 1; // Return partition index
} printf("Sorted array: ");
// QuickSort function documentation: Recursively sorts by printArray(arr, n);
partitioning
void quicksort(int arr[], int low, int high) { free(arr); // Free memory
if (low < high) { return 0;
// Partition the array }
int pi = partition(arr, low, high);

// Recursively sort elements before and after C:\Advanced Data Structures Lab\Lab-02>quick_sort.exe
partition
Enter the number of elements: 4
quicksort(arr, low, pi - 1); // Left sub-array
quicksort(arr, pi + 1, high); // Right sub-array Enter 4 elements: 12
} 1
} 2
// Print array function 27
void printArray(int arr[], int size) {
Original array: 12 1 2 27
for (int i = 0; i < size; i++)
printf("%d ", arr[i]); Sorted array: 1 2 12 27
printf("\n");
}
// Main - User input
int main() {
int n;
printf("Enter the number of elements: "); In Python Language:
scanf("%d", &n); # Quick Sort Algorithm in Python
# Documentation: Selects a pivot, partitions the array
int *arr = (int*)malloc(n * sizeof(int)); around it (smaller elements left, larger right), and
if (arr == NULL) { recursively sorts sub-arrays.
printf("Memory allocation failed!\n"); # Time Complexity: Average O(n log n), Worst O(n²) |
return 1; Space: O(log n) - recursive calls
def partition(arr, low, high): print("Original array:", arr)
"""
Partition function for quick sort. quicksort(arr, 0, len(arr) - 1)
Documentation: Uses last element as pivot. Rearranges
array so elements <= pivot are left, > pivot are right. print("Sorted array:", arr)
Returns the partition index (pivot's final position).
"""
pivot = arr[high] # Choose last element as pivot
i = low - 1 # Index of smaller element C:\Advanced Data Structures Lab\Lab-02>python quick_sort.py
Enter the number of elements: 3
for j in range(low, high):
if arr[j] <= pivot:
Enter 3 elements:
i += 1 23
# Swap arr[i] and arr[j] 1
arr[i], arr[j] = arr[j], arr[i] 22
Original array: [23, 1, 22]
# Swap pivot with i+1
arr[i + 1], arr[high] = arr[high], arr[i + 1]
Sorted array: [1, 22, 23]
return i + 1 # Return partition index
def quicksort(arr, low, high):
"""
Main quick sort function.
Documentation: Recursively sorts by partitioning: if Lab – 01
low < high, partition, then sort left and right sub-
arrays. Write a program to perform the following operations:
""" a) Insert an element into a binary search tree.
if low < high:
b) Delete an element from a binary search tree.
# Partition the array
pi = partition(arr, low, high) c) Search for a key element in a binary search
tree.
# Recursively sort elements before partition and
after
In C Language:
quicksort(arr, low, pi - 1) # Left sub-array
quicksort(arr, pi + 1, high) # Right sub-array
# Main part - User input #include <stdio.h>
if __name__ == "__main__": #include <stdlib.h>
n = int(input("Enter the number of elements: "))
arr = [] // BST Node structure
print(f"Enter {n} elements: ") struct Node {
for _ in range(n):
int data;
[Link](int(input()))
struct Node* left;
 struct Node* right;
}; // Find minimum value (leftmost node)
int minValue(struct Node* root) {
// Initialize empty BST (root = NULL) struct Node* current = root;
struct Node* initialize() { while (current && current->left != NULL) {
return NULL; current = current->left;
} }
if (current) return current->data;
// Create/Insert a new node (recursive) return -1; // Empty tree
struct Node* insert(struct Node* root, int data) { }
if (root == NULL) {
struct Node* newNode = (struct // Find maximum value (rightmost node)
Node*)malloc(sizeof(struct Node)); int maxValue(struct Node* root) {
newNode->data = data; struct Node* current = root;
newNode->left = NULL; while (current && current->right != NULL) {
newNode->right = NULL; current = current->right;
return newNode; }
} if (current) return current->data;
if (data < root->data) { return -1; // Empty tree
root->left = insert(root->left, data); }
} else if (data > root->data) {
root->right = insert(root->right, data); // Delete a node (three cases: leaf, one child, two
} children)
return root; struct Node* deleteNode(struct Node* root, int data) {
} if (root == NULL) return root;

// Search for a key if (data < root->data) {

struct Node* search(struct Node* root, int data) { root->left = deleteNode(root->left, data);
if (root == NULL || root->data == data) { } else if (data > root->data) {
return root; root->right = deleteNode(root->right, data);
} } else {
if (data < root->data) { // Node found
return search(root->left, data); if (root->left == NULL) { // Leaf or right child
} only
return search(root->right, data); struct Node* temp = root->right;
} free(root);
 return temp; }
} else if (root->right == NULL) { // Left child
only // Main function with UI (switch-case menu)
struct Node* temp = root->left; int main() {
free(root); struct Node* root = initialize(); // Start with empty
return temp; tree
} int choice, data;
// Two children: Get inorder successor (min in
right subtree) printf("=== Binary Search Tree Operations ===\n");
struct Node* temp = root->right; printf("1. Insert Node (Single)\n");
while (temp->left != NULL) { printf("2. Delete Node\n");
temp = temp->left; printf("3. Search Node\n");
} printf("4. Find Min Value\n");
root->data = temp->data; // Copy successor data printf("5. Find Max Value\n");
root->right = deleteNode(root->right, temp->data); printf("6. Inorder Traversal\n");
// Delete successor printf("7. Build Tree from Multiple Inputs (Existing
} Tree Load - Enter -1 to stop)\n");
return root; printf("0. Exit\n");
}
while (1) {
// Inorder traversal (Left-Root-Right, sorted order) printf("\nEnter your choice: ");
void inorder(struct Node* root) { scanf("%d", &choice);
if (root != NULL) {
inorder(root->left); switch (choice) {
printf("%d ", root->data); case 1:
inorder(root->right); printf("Enter data to insert: ");
} scanf("%d", &data);
} root = insert(root, data);
printf("%d inserted successfully!\n",
// Free tree memory (postorder) data);
void freeTree(struct Node* root) { break;
if (root != NULL) {
freeTree(root->left); case 2:
freeTree(root->right); printf("Enter data to delete: ");
free(root); scanf("%d", &data);
} if (search(root, data)) {
 root = deleteNode(root, data);
printf("%d deleted successfully!\n", case 6:
data); if (root) {
} else { printf("Inorder Traversal (Sorted):
printf("%d not found!\n", data); ");
} inorder(root);
break; printf("\n");
} else {
case 3: printf("Tree is empty!\n");
printf("Enter data to search: "); }
scanf("%d", &data); break;
if (search(root, data)) {
printf("%d found in the tree!\n", case 7:
data); printf("Enter values to build tree (space
} else { separated, -1 to stop): ");
printf("%d not found!\n", data); while (scanf("%d", &data) == 1 && data !=
} -1) {
break; root = insert(root, data);
printf("%d inserted. Continue...\n",
case 4: data);
if (root) { }
printf("Minimum value: %d\n", printf("Tree building complete!\n");
minValue(root)); break;
} else {
printf("Tree is empty!\n"); case 0:
} printf("Exiting... Freeing memory.\n");
break; freeTree(root);
return 0;
case 5:
if (root) { default:
printf("Maximum value: %d\n", printf("Invalid choice! Try again.\n");
maxValue(root)); }
} else { }
printf("Tree is empty!\n"); return 0;
} }
break;
In Python Language:
# Find maximum value (rightmost node)
class Node: def max_value(root):
def __init__(self, data): current = root
[Link] = data while current and [Link]:
[Link] = None current = [Link]
[Link] = None return [Link] if current else -1 # Empty tree

# Initialize empty BST (root = None) # Delete a node (three cases: leaf, one child, two
def initialize(): children)
return None def delete_node(root, data):
if root is None:
# Create/Insert a new node (recursive) return root
def insert(root, data):
if root is None: if data < [Link]:
return Node(data) [Link] = delete_node([Link], data)
if data < [Link]: elif data > [Link]:
[Link] = insert([Link], data) [Link] = delete_node([Link], data)
elif data > [Link]: else:
[Link] = insert([Link], data) # Node found
return root if [Link] is None: # Leaf or right child only
return [Link]
# Search for a key elif [Link] is None: # Left child only
def search(root, data): return [Link]
if root is None or [Link] == data:
return root # Two children: Get inorder successor (min in
if data < [Link]: right subtree)
return search([Link], data) temp = [Link]
return search([Link], data) while [Link]:
temp = [Link]
# Find minimum value (leftmost node) [Link] = [Link] # Copy successor data
def min_value(root): [Link] = delete_node([Link], [Link]) #
current = root Delete successor
while current and [Link]:
current = [Link] return root
return [Link] if current else -1 # Empty tree
# Inorder traversal (Left-Root-Right, sorted order) print(f"{data} inserted successfully!")
def inorder(root):
if root: elif choice == 2:
inorder([Link]) data = int(input("Enter data to delete: "))
print([Link], end=' ') if search(root, data):
inorder([Link]) root = delete_node(root, data)
print(f"{data} deleted successfully!")
# Optional: Delete tree (Python GC handles, but for else:
completeness) print(f"{data} not found!")
def delete_tree(root):
if root: elif choice == 3:
delete_tree([Link]) data = int(input("Enter data to search: "))
delete_tree([Link]) if search(root, data):
del root # Or root = None print(f"{data} found in the tree!")
else:
# Main function with UI (if-elif menu loop) print(f"{data} not found!")
def main():
root = initialize() # Start with empty tree elif choice == 4:
if root:
print("=== Binary Search Tree Operations ===") print(f"Minimum value:
print("1. Insert Node") {min_value(root)}")
print("2. Delete Node") else:
print("3. Search Node") print("Tree is empty!")
print("4. Find Min Value")
print("5. Find Max Value") elif choice == 5:
print("6. Inorder Traversal") if root:
print("7. Build Tree from Multiple Inputs (Enter -1 to print(f"Maximum value:
stop)") {max_value(root)}")
print("0. Exit") else:
print("Tree is empty!")
while True:
choice = int(input("\nEnter your choice: ")) elif choice == 6:
if root:
if choice == 1: print("Inorder Traversal (Sorted): ",
data = int(input("Enter data to insert: ")) end='')
root = insert(root, data) inorder(root)
 print()
else:
print("Tree is empty!")

elif choice == 7:
print("Enter values to build tree (-1 to
stop): ")
while True:
try:
data = int(input())
if data == -1:
break
root = insert(root, data)
print(f"{data} inserted.
Continue...")
except ValueError:
print("Invalid input! Enter
integer.")
print("Tree building complete!")

elif choice == 0:
print("Exiting... Deleting tree.")
delete_tree(root)
break

else:
print("Invalid choice! Try again.")

if __name__ == "__main__":
main()