Scribd
Upload
8 views13 pages

Data Structures: Linked Lists & Heaps

The document contains a series of programming exercises related to data structures and algorithms, specifically focusing on linked lists, heaps, and the Josephus problem. It includes code implementations for finding and deleting nodes in a linked list, creating max and min heaps, deleting the root of a max heap, and implementing the heap sort algorithm. Each section provides code examples and outputs demonstrating the functionality of the implemented algorithms.

Uploaded by

adarsh171208
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views13 pages

Data Structures: Linked Lists & Heaps

The document contains a series of programming exercises related to data structures and algorithms, specifically focusing on linked lists, heaps, and the Josephus problem. It includes code implementations for finding and deleting nodes in a linked list, creating max and min heaps, deleting the root of a max heap, and implementing the heap sort algorithm. Each section provides code examples and outputs demonstrating the functionality of the implemented algorithms.

Uploaded by

adarsh171208
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Department of Electrical Engineering Autumn 2025

EEO 101: DATA STRUCTURES

Worksheet – 6

Name: Adarsh Tiwari


Enrollment: 24112005
Department:Chemical engineering
Year: 2
Batch:1

1. Write a function to find kth node in a linked list represented by a binary


tree. Using this function write another function to delete Kth node of the list.
#font=Times New Roman, font size=12
CODE:
#include <iostream>
using namespace std;

struct Node {
int data;
Node* left; // acts as 'next'
Node* right; // unused
};

Node* createNode(int value) {


Node* newNode = new Node;
newNode->data = value;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}

Node* findKthNode(Node* head, int k) {


int count = 1;
Node* temp = head;
while (temp && count < k) {
temp = temp->left;
count++;
}
return (count == k) ? temp : nullptr;
}

void deleteKthNode(Node*& head, int k) {


if (!head) return;

if (k == 1) {
Node* temp = head;
head = head->left;
delete temp;
return;
}

Node* prev = findKthNode(head, k - 1);


if (!prev || !prev->left) return;

Node* del = prev->left;


prev->left = del->left;
delete del;
}

void printList(Node* head) {


while (head) {
cout << head->data << " ";
head = head->left;
}
cout << endl;
}

int main() {
Node* head = createNode(10);
head->left = createNode(20);
head->left->left = createNode(30);
head->left->left->left = createNode(40);

cout << "Original list: ";


printList(head);

int k = 3;
Node* kth = findKthNode(head, k);
if (kth)
cout << "The " << k << "rd node is: " << kth->data << endl;

deleteKthNode(head, k);

cout << "After deleting " << k << "rd node: ";
printList(head);

return 0;
}
OUTPUT:

2. Use the functions developed in 1 to implement the Josephus Problem.


CODE:
#include <iostream>
using namespace std;

struct Node {
int data;
Node* left; // acts as 'next'
Node* right; // unused
};

Node* createNode(int value) {


Node* newNode = new Node;
newNode->data = value;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}

Node* findKthNode(Node* head, int k) {


int count = 1;
Node* temp = head;
while (temp && count < k) {
temp = temp->left;
count++;
}
return (count == k) ? temp : nullptr;
}

void deleteKthNode(Node*& head, int k) {


if (!head) return;
if (k == 1) {
Node* temp = head;
head = head->left;
delete temp;
return;
}
Node* prev = findKthNode(head, k - 1);
if (!prev || !prev->left) return;
Node* del = prev->left;
prev->left = del->left;
delete del;
}

void printList(Node* head) {


Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->left;
}
cout << endl;
}

// Function to create a circular linked list


Node* createCircularList(int n) {
Node* head = createNode(1);
Node* temp = head;
for (int i = 2; i <= n; i++) {
temp->left = createNode(i);
temp = temp->left;
}
temp->left = head; // make it circular
return head;
}

// Josephus Problem using previously defined functions


int josephus(int n, int k) {
Node* head = createCircularList(n);
Node* ptr = head;

while (ptr->left != ptr) { // more than one node remains


for (int i = 1; i < k - 1; i++)
ptr = ptr->left; // move (k-1) steps
Node* temp = ptr->left; // kth node
ptr->left = temp->left; // delete kth node
delete temp;
ptr = ptr->left; // move to next node
}
int survivor = ptr->data;
delete ptr;
return survivor;
}

int main() {
int n = 7, k = 3;
cout << "Josephus Problem (n=" << n << ", k=" << k << ")\n";
cout << "Survivor: " << josephus(n, k) << endl;
return 0;
}
OUTPUT:

3. Write a function to create a Max Heap Tree.


CODE:
#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at index i


void heapify(int arr[], int n, int i) {
int largest = i; // root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child

if (left < n && arr[left] > arr[largest])


largest = left;

if (right < n && arr[right] > arr[largest])


largest = right;

if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

// Function to build a Max Heap


void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}

void printHeap(int arr[], int n) {


for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {
int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";


printHeap(arr, n);

buildMaxHeap(arr, n);

cout << "Max Heap: ";


printHeap(arr, n);

return 0;
}

OUTPUT:

4. Write a function to create a Min Heap Tree.

CODE:
#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at index i


void heapify(int arr[], int n, int i) {
int smallest = i; // root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child

if (left < n && arr[left] < arr[smallest])


smallest = left;

if (right < n && arr[right] < arr[smallest])


smallest = right;

if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(arr, n, smallest);
}
}
// Function to build a Min Heap
void buildMinHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}

void printHeap(int arr[], int n) {


for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {
int arr[] = {9, 5, 6, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";


printHeap(arr, n);

buildMinHeap(arr, n);

cout << "Min Heap: ";


printHeap(arr, n);

return 0;
}

OUTPUT:

5. Write a function delete_root( ) to delete the root of a Max heap tree.

CODE:

#include <iostream>
using namespace std;

// Heapify function for Max Heap


void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])


largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;

if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

// Function to build a Max Heap


void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}

// Function to delete the root from Max Heap


int delete_root(int arr[], int& n) {
if (n <= 0)
return -1;

int root = arr[0];


arr[0] = arr[n - 1];
n--;

heapify(arr, n, 0);
return root;
}

void printHeap(int arr[], int n) {


for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {
int arr[] = {20, 18, 15, 13, 10, 12, 9};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original Max Heap: ";


printHeap(arr, n);

int deleted = delete_root(arr, n);

cout << "Deleted root: " << deleted << endl;


cout << "Heap after deletion: ";
printHeap(arr, n);

return 0;
}

OUTPUT:

6. Making use of the functions developed in 3,4 and 5 write a function to


implement Heap sort algorithm to sort a given array. Your function should
receive a flag SORT to decide ascending order or descending order sorting as
follows
SORT = 1 Ascending order SORT = 0 Descending order.

CODE:
#include <iostream>
using namespace std;

// Heapify for Max Heap


void maxHeapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])


largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;

if (largest != i) {
swap(arr[i], arr[largest]);
maxHeapify(arr, n, largest);
}
}

// Heapify for Min Heap


void minHeapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] < arr[smallest])


smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(arr[i], arr[smallest]);
minHeapify(arr, n, smallest);
}
}

// Build Max Heap


void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
}

// Build Min Heap


void buildMinHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
}

// Delete root and adjust heap


void delete_root_max(int arr[], int& n) {
arr[0] = arr[n - 1];
n--;
maxHeapify(arr, n, 0);
}

void delete_root_min(int arr[], int& n) {


arr[0] = arr[n - 1];
n--;
minHeapify(arr, n, 0);
}

// Heap Sort function


void heapSort(int arr[], int n, int SORT) {
if (SORT == 1) { // Ascending order using Max Heap
buildMaxHeap(arr, n);
for (int i = n - 1; i >= 1; i--) {
swap(arr[0], arr[i]);
maxHeapify(arr, i, 0);
}
}
else { // Descending order using Min Heap
buildMinHeap(arr, n);
for (int i = n - 1; i >= 1; i--) {
swap(arr[0], arr[i]);
minHeapify(arr, i, 0);
}
}
}

void printArray(int arr[], int n) {


for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";


printArray(arr, n);

int SORT = 1; // 1 for Ascending, 0 for Descending


heapSort(arr, n, SORT);

if (SORT == 1)
cout << "Sorted in Ascending order: ";
else
cout << "Sorted in Descending order: ";

printArray(arr, n);
return 0;
}
OUTPUT:

You might also like