Task 1: Heap sort using Heapify method with linked list.

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtBeginning(Node*& head, int val) {

Node* newNode = new Node(val);

newNode->next = head;

head = newNode;

void printList(Node* head) {

while (head) {

cout << head->data << " ";

head = head->next;

cout << endl;

void swapData(Node* a, Node* b) {

int temp = a->data;

a->data = b->data;
 b->data = temp;

void heapify(Node* root, bool isMaxHeap) {

Node* target = root;

Node* left = root->next;

Node* right = left ? left->next : nullptr;

if (left && ((isMaxHeap && left->data > target->data) || (!isMaxHeap && left->data < target->data)))

target = left;

if (right && ((isMaxHeap && right->data > target->data) || (!isMaxHeap && right->data < target-
>data)))

target = right;

if (target != root) {

swapData(target, root);

heapify(target, isMaxHeap);

void buildHeap(Node* head, bool isMaxHeap) {

for (Node* current = head; current != nullptr; current = current->next)

heapify(current, isMaxHeap);

void heapSort(Node*& head, bool isMaxHeap) {

buildHeap(head, isMaxHeap);

Node* sorted = nullptr;

 while (head) {

Node* next = head->next;

head->next = sorted;

sorted = head;

head = next;

head = sorted;

int main() {

Node* headMinHeap = nullptr;

insertAtBeginning(headMinHeap, 3);

insertAtBeginning(headMinHeap, 5);

insertAtBeginning(headMinHeap, 8);

insertAtBeginning(headMinHeap, 10);

insertAtBeginning(headMinHeap, 2);

cout << "Linked List before Heap Sort (Min Heap): ";

printList(headMinHeap);

heapSort(headMinHeap, false);

cout << "Linked List after Heap Sort (Min Heap): ";

printList(headMinHeap);

Node* headMaxHeap = nullptr;

insertAtBeginning(headMaxHeap, 3);

insertAtBeginning(headMaxHeap, 5);
 insertAtBeginning(headMaxHeap, 8);

insertAtBeginning(headMaxHeap, 10);

insertAtBeginning(headMaxHeap, 2);

cout << "\nLinked List before Heap Sort (Max Heap): ";

printList(headMaxHeap);

heapSort(headMaxHeap, true);

cout << "Linked List after Heap Sort (Max Heap): ";

printList(headMaxHeap);

return 0;

}
Task 2:Insertion sort with linked list

#include <bits/stdc++.h>
using namespace std;

struct Node
{
int val;
struct Node* next;
Node(int x)
{
val = x;
next = NULL;
}
};

class LinkedlistIS
{
public:
Node* head;
Node* sorted;
void push(int val)
{
Node* newnode = new Node(val);
newnode->next = head;
head = newnode;
}

void insertionSort(Node* headref)

{
sorted = NULL;
Node* current = headref;

while (current != NULL)

{
Node* next = current->next;
sortedInsert(current);
current = next;
}

head = sorted;
}
 void sortedInsert(Node* newnode)
{
if (sorted == NULL || sorted->val >= newnode->val)
{
newnode->next = sorted;
sorted = newnode;
}
else
{
Node* current = sorted;

while (current->next != NULL && current->next->val <

newnode->val)
{
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
}

void printlist(Node* head)

 {
while (head != NULL)
{
cout << head->val << endl;
head = head->next;
}
}
};

int main()
{
LinkedlistIS list;
list.head = NULL;
list.push(9);
list.push(22);
list.push(6);
list.push(3);
list.push(40);
cout << "Linked List before sorting" << endl;
list.printlist(list.head);
cout << endl;
list.insertionSort(list.head);
 cout << "Linked List After sorting" << endl;
list.printlist(list.head);
}
Task 3: Implement Huffman code to reduce the size of a msg

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

struct Node {
char data;
int freq;
Node* left, *right;

Node(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr)

{}
};

struct Compare {
bool operator()(Node* l, Node* r) {
return l->freq > r->freq;
}
};

void assignCodes(Node* root, string code, unordered_map<char, string>&

huffmanCode) {
if (root == nullptr)
return;

if (!root->left && !root->right) {

huffmanCode[root->data] = code;
}
 assignCodes(root->left, code + "0", huffmanCode);
assignCodes(root->right, code + "1", huffmanCode);
}

void buildHuffmanTree(string message, unordered_map<char, string>&

huffmanCode) {
unordered_map<char, int> freq;
for (char ch : message) {
freq[ch]++;
}

priority_queue<Node*, vector<Node*>, Compare> pq;

for (auto& pair : freq) {
pq.push(new Node(pair.first, pair.second));
}

while (pq.size() > 1) {

Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();

Node* newNode = new Node('$', left->freq + right->freq);

newNode->left = left;
newNode->right = right;
pq.push(newNode);
}

Node* root = pq.top();

assignCodes(root, "", huffmanCode);

}

int main() {
string messages[4] = {"hello", "world", "openai", "chatbot"};

unordered_map<char, string> huffmanCode;

int = 0;

originalSize = 0;
int encodedSize
for (int i = 0; i < 4; ++i) {
string message = messages[i];
originalSize += message.size();

buildHuffmanTree(message, huffmanCode);
string encodedMessage = "";
for (char ch : message) {
encodedMessage += huffmanCode[ch];
}
encodedSize += encodedMessage.size();

cout << "Original Message: " << message << endl;

cout << "Encoded Message: " << encodedMessage << endl;
}

cout << "Original Total Size: " << originalSize << " bits" << endl;
cout << "Encoded Total Size: " << encodedSize << " bits" << endl;

return 0;
}