Session 4

import heapq

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def solve_huffman():
    # 1. Initialize data from the problem table
    data = {'A': 10, 'B': 7, 'I': 15, 'M': 8, 'S': 10, 'X': 5, 'Z': 2}
    heap = [Node(c, f) for c, f in data.items()]
    heapq.heapify(heap)

    print("--- STEP-BY-STEP MERGING (GREEDY STEPS) ---")
    step = 1
    while len(heap) > 1:
        # Extract two smallest frequencies
        n1 = heapq.heappop(heap)
        n2 = heapq.heappop(heap)

        # Merge them
        merged = Node(None, n1.freq + n2.freq)
        merged.left = n1
        merged.right = n2

        print(f"Step {step}: Merged {n1.char or 'Node'}({n1.freq}) and "
              f"{n2.char or 'Node'}({n2.freq}) -> New Node({merged.freq})")

        heapq.heappush(heap, merged)
        step += 1

    # 2. Generate Codes and Print Table
    root = heap[0]
    codes = {}

    def generate_codes(node, current_code):
        if node:
            if node.char:
                codes[node.char] = current_code
            generate_codes(node.left, current_code + "0")
            generate_codes(node.right, current_code + "1")

    generate_codes(root, "")

    print("\n--- FINAL OPTIMAL BINARY PREFIX CODES ---")
    print(f"{'Letter':<10} | {'Frequency':<10} | {'Huffman Code':<15}")
    print("-" * 40)
    for char in sorted(data.keys()):
        print(f"{char:<10} | {data[char]:<10} | {codes[char]:<15}")

solve_huffman()

#include <stdio.h>
#include <stdlib.h>

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

struct Node* createNode(char data, int freq) {
    struct Node* n = (struct Node*)malloc(sizeof(struct Node));
    n->data = data; n->freq = freq;
    n->left = n->right = NULL;
    return n;
}

void printCodes(struct Node* root, int arr[], int top) {
    if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); }
    if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); }
    if (!root->left && !root->right) {
        printf("%-7c | %-7d | ", root->data, root->freq);
        for (int i = 0; i < top; i++) printf("%d", arr[i]);
        printf("\n");
    }
}

int main() {
    char letters[] = {'A', 'B', 'I', 'M', 'S', 'X', 'Z'};
    int freqs[] = {10, 7, 15, 8, 10, 5, 2};
    struct Node* nodes[7];

    for (int i = 0; i < 7; i++) nodes[i] = createNode(letters[i], freqs[i]);

    printf("--- STEP-BY-STEP MERGING ---\n");
    int size = 7;
    while (size > 1) {
        int m1 = 0, m2 = 1;
        if (nodes[m1]->freq > nodes[m2]->freq) { int t = m1; m1 = m2; m2 = t; }
        for (int i = 2; i < size; i++) {
            if (nodes[i]->freq < nodes[m1]->freq) { m2 = m1; m1 = i; }
            else if (nodes[i]->freq < nodes[m2]->freq) { m2 = i; }
        }

        struct Node* parent = createNode('$', nodes[m1]->freq + nodes[m2]->freq);
        parent->left = nodes[m1]; parent->right = nodes[m2];
        printf("Merged %d + %d = %d\n", nodes[m1]->freq, nodes[m2]->freq, parent->freq);

        nodes[m1] = parent;
        nodes[m2] = nodes[size - 1];
        size--;
    }

    printf("\n--- FINAL TABLE ---\n%-7s | %-7s | %-12s\n", "Letter", "Freq", "Code");
    printf("-----------------------------\n");
    int path[10];
    printCodes(nodes[0], path, 0);
    return 0;
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Node {
    freq: i32,
    char: Option<char>,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.freq.cmp(&other.freq)
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn traverse(node: &Node, code: String) {
    if let Some(c) = node.char {
        println!("{:<7} | {:<7} | {}", c, node.freq, code);
    } else {
        if let Some(ref l) = node.left {
            traverse(l, code.clone() + "0");
        }
        if let Some(ref r) = node.right {
            traverse(r, code + "1");
        }
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    let items = vec![
        ('A', 10),
        ('B', 7),
        ('I', 15),
        ('M', 8),
        ('S', 10),
        ('X', 5),
        ('Z', 2),
    ];

    for (c, f) in items {
        heap.push(Reverse(Node {
            freq: f,
            char: Some(c),
            left: None,
            right: None,
        }));
    }

    println!("--- MERGING STEPS ---");
    while heap.len() > 1 {
        let Reverse(n1) = heap.pop().unwrap();
        let Reverse(n2) = heap.pop().unwrap();
        let parent = Node {
            freq: n1.freq + n2.freq,
            char: None,
            left: Some(Box::new(n1)),
            right: Some(Box::new(n2)),
        };
        println!(
            "Merged: {} + {} = {}",
            parent.left.as_ref().unwrap().freq,
            parent.right.as_ref().unwrap().freq,
            parent.freq
        );
        heap.push(Reverse(parent));
    }

    let Reverse(root) = heap.pop().unwrap();
    println!(
        "\n--- FINAL TABLE ---\n{:<7} | {:<7} | {}",
        "Letter", "Freq", "Code"
    );
    println!("-----------------------------");
    traverse(&root, "".to_string());
}

import heapq

class Node:
    def __init__(self, freq, char=None):
        self.freq = freq
        self.char = char
        self.left = None
        self.right = None

    # Required for heapq to compare nodes by frequency
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_dict):
    """Builds Huffman Tree using a Min-Heap"""
    heap = [Node(f, c) for c, f in freq_dict.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    return heap[0] if heap else None

def generate_codes(root, current_code="", codes=None):
    """DFS traversal to assign 0/1 codes"""
    if codes is None:
        codes = {}
    if root is None:
        return
    if root.char is not None:  # Leaf node
        codes[root.char] = current_code
        return
    generate_codes(root.left, current_code + "0", codes)
    generate_codes(root.right, current_code + "1", codes)
    return codes

def main():
    freq = {'A': 15, 'B': 25, 'C': 5, 'D': 7, 'E': 10, 'F': 13, 'G': 9}
    root = build_huffman_tree(freq)
    codes = generate_codes(root)

    # Calculate average bits
    total_bits = sum(freq[c] * len(codes[c]) for c in codes)
    total_freq = sum(freq.values())
    avg_bits = total_bits / total_freq

    print("Huffman Codes:")
    for char in sorted(codes.keys()):
        print(f"{char}: {codes[char]}")
    print(f"\nAverage bits per character: {avg_bits:.2f}")

if __name__ == "__main__":
    main()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

// Simulated Priority Queue
Node* pq[20];
int pq_size = 0;
int active_nodes = 0;

Node* newNode(int freq, char data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->freq = freq;
    n->data = data;
    n->left = n->right = NULL;
    pq[pq_size++] = n;
    active_nodes++;
    return n;
}

// Extract minimum frequency node
Node* extractMin() {
    int minIdx = -1;
    for (int i = 0; i < pq_size; i++) {
        if (pq[i] != NULL) {
            if (minIdx == -1 || pq[i]->freq < pq[minIdx]->freq)
                minIdx = i;
        }
    }
    if (minIdx == -1) return NULL;
    Node* minNode = pq[minIdx];
    pq[minIdx] = NULL;
    active_nodes--;
    return minNode;
}

void printCodes(Node* root, char arr[], int top) {
    if (root->left) {
        arr[top] = '0';
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = '1';
        printCodes(root->right, arr, top + 1);
    }
    if (root->data != '\0') { // Leaf node
        arr[top] = '\0';
        printf("%c: %s\n", root->data, arr);
    }
}

// Calculate total weighted path length for average
int calculateTotalBits(Node* root, int depth) {
    if (root == NULL) return 0;
    if (root->data != '\0') return root->freq * depth;
    return calculateTotalBits(root->left, depth + 1) +
           calculateTotalBits(root->right, depth + 1);
}

int main() {
    char chars[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    int freqs[] = {15, 25, 5, 7, 10, 13, 9};
    int n = 7, totalFreq = 0;

    for (int i = 0; i < n; i++) {
        newNode(freqs[i], chars[i]);
        totalFreq += freqs[i];
    }

    // Build Huffman Tree
    while (active_nodes > 1) {
        Node* left = extractMin();
        Node* right = extractMin();
        if (!left || !right) break;

        Node* merged = newNode(left->freq + right->freq, '\0');
        merged->left = left;
        merged->right = right;
    }

    Node* root = extractMin();
    char code[50];
    printf("Huffman Codes:\n");
    printCodes(root, code, 0);

    int totalBits = calculateTotalBits(root, 0);
    double avgBits = (double)totalBits / totalFreq;
    printf("\nAverage bits per character: %.2f\n", avgBits);

    return 0;
}

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug)]
struct Node {
    freq: usize,
    ch: Option<char>,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

// Implement Ord for BinaryHeap (defaults to max-heap)
// We reverse comparison to simulate a min-heap based on frequency
impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.freq == other.freq
    }
}
impl Eq for Node {}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.freq.cmp(&self.freq)) // Reverse order
    }
}
impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        other.freq.cmp(&self.freq)
    }
}

fn build_tree(freqs: &[(char, usize)]) -> Box<Node> {
    let mut heap = BinaryHeap::new();
    for &(ch, f) in freqs {
        heap.push(Box::new(Node {
            freq: f,
            ch: Some(ch),
            left: None,
            right: None,
        }));
    }

    while heap.len() > 1 {
        let left = heap.pop().unwrap();
        let right = heap.pop().unwrap();
        heap.push(Box::new(Node {
            freq: left.freq + right.freq,
            ch: None,
            left: Some(left),
            right: Some(right),
        }));
    }
    heap.pop().unwrap()
}

fn generate_codes(node: &Box<Node>, current: &str, codes: &mut Vec<(char, String)>) {
    if let Some(ch) = node.ch {
        codes.push((ch, current.to_string()));
        return;
    }
    if let Some(ref left) = node.left {
        generate_codes(left, &format!("{}0", current), codes);
    }
    if let Some(ref right) = node.right {
        generate_codes(right, &format!("{}1", current), codes);
    }
}

fn main() {
    let freqs = [
        ('A', 15),
        ('B', 25),
        ('C', 5),
        ('D', 7),
        ('E', 10),
        ('F', 13),
        ('G', 9),
    ];
    let root = build_tree(&freqs);

    let mut codes: Vec<(char, String)> = Vec::new();
    generate_codes(&root, "", &mut codes);
    codes.sort_by_key(|c| c.0); // Sort alphabetically for clean output

    let total_freq: usize = freqs.iter().map(|(_, f)| f).sum();
    let total_bits: usize = codes
        .iter()
        .map(|(ch, code)| {
            let f = freqs.iter().find(|(c, _)| *c == *ch).unwrap().1;
            f * code.len()
        })
        .sum();

    println!("Huffman Codes:");
    for (ch, code) in &codes {
        println!("{}: {}", ch, code);
    }
    println!(
        "\nAverage bits per character: {:.2}",
        total_bits as f64 / total_freq as f64
    );
}

import heapq


class Node:
    """Huffman Tree Node"""

    def __init__(self, freq, char=None):
        self.freq = freq
        self.char = char  # None for internal nodes
        self.left = None
        self.right = None

    def __lt__(self, other):
        """Enable comparison for heapq (min-heap by frequency)"""
        return self.freq < other.freq


def build_huffman_tree(freq_dict):
    """Build Huffman tree using priority queue (min-heap)"""
    heap = [Node(f, c) for c, f in freq_dict.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        # Extract two smallest frequency nodes
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # Create merged internal node
        merged = Node(left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    return heap[0] if heap else None


def generate_codes(node, current_code="", codes=None):
    """DFS traversal to assign binary codes (0=left, 1=right)"""
    if codes is None:
        codes = {}
    if node is None:
        return codes
    if node.char is not None:  # Leaf node
        codes[node.char] = current_code
        return codes
    generate_codes(node.left, current_code + "0", codes)
    generate_codes(node.right, current_code + "1", codes)
    return codes


def calculate_avg_bits(codes, freq_dict):
    """Calculate weighted average bits per character"""
    total_bits = sum(freq_dict[c] * len(codes[c]) for c in codes)
    total_freq = sum(freq_dict.values())
    return total_bits / total_freq


def main():
    # Input frequencies
    freq = {
        ":": 80,
        " ": 500,
        "\n": 110,
        ",": 500,
        "0": 300,
        "1": 200,
        "2": 150,
        "3": 60,
        "4": 180,
        "5": 240,
        "6": 170,
        "7": 200,
        "8": 202,
    }

    # Build tree and generate codes
    root = build_huffman_tree(freq)
    codes = generate_codes(root)

    # Display results
    print("Huffman Codes:")
    for char in sorted(codes.keys(), key=lambda c: freq[c], reverse=True):
        display = repr(char) if char in [" ", "\n", ":", ","] else char
        print(f"{display:>6} (freq={freq[char]:4d}): {codes[char]}")

    avg = calculate_avg_bits(codes, freq)
    print(f"\nAverage bits per character: {avg:.2f}")
    print(f"Total frequency: {sum(freq.values())}")
    print(f"Total bits for encoded file: {sum(freq[c] * len(codes[c]) for c in codes)}")


if __name__ == "__main__":
    main()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHARS 13
#define MAX_CODE_LEN 20

// Huffman Tree Node
typedef struct Node {
    int freq;
    char data;
    struct Node *left, *right;
} Node;

// Priority Queue (simple array-based min-heap simulation)
Node* pq[100];
int pq_size = 0;

// Create new node
Node* newNode(int freq, char data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->freq = freq;
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

// Insert into priority queue (maintain sorted order for simplicity)
void pq_insert(Node* node) {
    int i = pq_size - 1;
    while (i >= 0 && pq[i]->freq > node->freq) {
        pq[i + 1] = pq[i];
        i--;
    }
    pq[i + 1] = node;
    pq_size++;
}

// Extract minimum frequency node
Node* pq_extract_min() {
    if (pq_size == 0) return NULL;
    return pq[pq_size--];
}

// Generate and print codes via DFS
void printCodes(Node* root, char arr[], int top, int* total_bits, int freq_map[], char chars[]) {
    if (root->left) {
        arr[top] = '0';
        printCodes(root->left, arr, top + 1, total_bits, freq_map, chars);
    }
    if (root->right) {
        arr[top] = '1';
        printCodes(root->right, arr, top + 1, total_bits, freq_map, chars);
    }
    // Leaf node: print code and accumulate bits
    if (root->data != '\0') {
        arr[top] = '\0';
        // Find frequency for this character
        for (int i = 0; i < MAX_CHARS; i++) {
            if (chars[i] == root->data) {
                int len = top;
                *total_bits += freq_map[i] * len;
                // Handle special character display
                if (root->data == ' ') printf("  ' '  ");
                else if (root->data == '\n') printf(" '\\n' ");
                else if (root->data == ':') printf("  ':'  ");
                else if (root->data == ',') printf("  ','  ");
                else printf("  '%c'  ", root->data);
                printf("(freq=%4d): %s\n", freq_map[i], arr);
                break;
            }
        }
    }
}

int main() {
    // Character-frequency pairs
    char chars[MAX_CHARS] = {':', ' ', '\n', ',', '0', '1', '2', '3', '4', '5', '6', '7', '8'};
    int freqs[MAX_CHARS] = {80, 500, 110, 500, 300, 200, 150, 60, 180, 240, 170, 200, 202};
    int total_freq = 0;

    // Initialize priority queue with leaf nodes
    for (int i = 0; i < MAX_CHARS; i++) {
        pq_insert(newNode(freqs[i], chars[i]));
        total_freq += freqs[i];
    }

    // Build Huffman Tree
    while (pq_size > 1) {
        Node* left = pq_extract_min();
        Node* right = pq_extract_min();
        Node* merged = newNode(left->freq + right->freq, '\0');
        merged->left = left;
        merged->right = right;
        pq_insert(merged);
    }

    Node* root = pq_extract_min();
    char code[MAX_CODE_LEN];
    int total_bits = 0;

    printf("Huffman Codes:\n");
    printCodes(root, code, 0, &total_bits, freqs, chars);

    double avg_bits = (double)total_bits / total_freq;
    printf("\nAverage bits per character: %.2f\n", avg_bits);
    printf("Total frequency: %d\n", total_freq);
    printf("Total bits for encoded file: %d\n", total_bits);

    return 0;
}

use std::cmp::Ordering;
use std::collections::BinaryHeap;

// Huffman Tree Node
#[derive(Debug)]
struct Node {
    freq: usize,
    ch: Option<char>,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

// Implement ordering for BinaryHeap (min-heap by frequency)
impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.freq == other.freq
    }
}
impl Eq for Node {}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        // Reverse for min-heap behavior
        Some(other.freq.cmp(&self.freq))
    }
}
impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        other.freq.cmp(&self.freq)
    }
}

fn build_tree(freqs: &[(char, usize)]) -> Box<Node> {
    let mut heap = BinaryHeap::new();

    // Push all leaf nodes
    for &(ch, f) in freqs {
        heap.push(Box::new(Node {
            freq: f,
            ch: Some(ch),
            left: None,
            right: None,
        }));
    }

    // Merge nodes until one root remains
    while heap.len() > 1 {
        let left = heap.pop().unwrap();
        let right = heap.pop().unwrap();
        heap.push(Box::new(Node {
            freq: left.freq + right.freq,
            ch: None,
            left: Some(left),
            right: Some(right),
        }));
    }
    heap.pop().unwrap()
}

fn generate_codes(node: &Box<Node>, current: &str, codes: &mut Vec<(char, String)>) {
    if let Some(ch) = node.ch {
        codes.push((ch, current.to_string()));
        return;
    }
    if let Some(ref left) = node.left {
        generate_codes(left, &format!("{}0", current), codes);
    }
    if let Some(ref right) = node.right {
        generate_codes(right, &format!("{}1", current), codes);
    }
}

fn display_char(ch: char) -> String {
    match ch {
        ' ' => "' '".to_string(),
        '\n' => "'\\n'".to_string(),
        ':' => "':'".to_string(),
        ',' => "','".to_string(),
        _ => format!("'{}'", ch),
    }
}

fn main() {
    // Input: (character, frequency) pairs
    let freqs = [
        (':', 80),
        (' ', 500),
        ('\n', 110),
        (',', 500),
        ('0', 300),
        ('1', 200),
        ('2', 150),
        ('3', 60),
        ('4', 180),
        ('5', 240),
        ('6', 170),
        ('7', 200),
        ('8', 202),
    ];

    let root = build_tree(&freqs);
    let mut codes: Vec<(char, String)> = Vec::new();
    generate_codes(&root, "", &mut codes);

    // Sort by frequency (descending) for display
    codes.sort_by(|a, b| {
        let fa = freqs.iter().find(|(c, _)| *c == a.0).unwrap().1;
        let fb = freqs.iter().find(|(c, _)| *c == b.0).unwrap().1;
        fb.cmp(&fa)
    });

    // Calculate statistics
    let total_freq: usize = freqs.iter().map(|(_, f)| f).sum();
    let total_bits: usize = codes
        .iter()
        .map(|(ch, code)| {
            let f = freqs.iter().find(|(c, _)| *c == *ch).unwrap().1;
            f * code.len()
        })
        .sum();

    println!("Huffman Codes:");
    for (ch, code) in &codes {
        let f = freqs.iter().find(|(c, _)| *c == *ch).unwrap().1;
        println!("{:>6} (freq={:4o}): {}", display_char(*ch), f, code);
    }

    let avg_bits = total_bits as f64 / total_freq as f64;
    println!("\nAverage bits per character: {}", avg_bits);
    println!("Total frequency: {}", total_freq);
    println!("Total bits for encoded file: {}", total_bits);
}