Greedy Algorithms

from fractions import Fraction

def fractional_knapsack(items, capacity):
    """
    Greedy: Take items by value/weight ratio
    Can take fractions of items
    
    Time: O(n log n)
    """
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    if any(weight <= 0 or value < 0 for weight, value in items):
        raise ValueError("expected positive weights and non-negative values")
    # Fraction keeps the ordering exact even when two large ratios round to
    # the same binary floating-point value.
    ordered = sorted(
        items,
        key=lambda item: (-Fraction(item[1], item[0]), item[0], item[1]),
    )
    
    total_value = 0
    remaining = capacity
    
    for weight, value in ordered:
        if remaining == 0:
            break
        if remaining >= weight:
            # Take whole item
            total_value += value
            remaining -= weight
        else:
            # Take fraction
            total_value += value * (remaining / weight)
            break
    
    return total_value

items = [(10, 60), (20, 100), (30, 120)]  # (weight, value)
capacity = 50
print(f"Max value: {fractional_knapsack(items, capacity)}")
# Output: Max value: 240.0

import java.util.*;

public class FractionalKnapsack {
    static class Item {
        final int weight, value;
        
        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
        
    }
    
    /**
     * Greedy: Take items by value/weight ratio
     * Can take fractions of items
     * 
     * Time: O(n log n)
     */
    public static double fractionalKnapsack(List<Item> items, int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("negative capacity");
        for (Item item : items) {
            if (item.weight <= 0 || item.value < 0) throw new IllegalArgumentException("bad item");
        }
        List<Item> ordered = new ArrayList<>(items);
        ordered.sort((first, second) -> {
            long left = (long) first.value * second.weight;
            long right = (long) second.value * first.weight;
            int byDensity = Long.compare(right, left); // descending value / weight
            if (byDensity != 0) return byDensity;
            int byWeight = Integer.compare(first.weight, second.weight);
            return byWeight != 0 ? byWeight : Integer.compare(first.value, second.value);
        });
        
        double totalValue = 0;
        int remaining = capacity;
        
        for (Item item : ordered) {
            if (remaining == 0) break;
            if (remaining >= item.weight) {
                // Take whole item
                totalValue += item.value;
                remaining -= item.weight;
            } else {
                // Take fraction
                totalValue += item.value * ((double) remaining / item.weight);
                break;
            }
        }
        
        return totalValue;
    }
    
    public static void main(String[] args) {
        List<Item> items = Arrays.asList(
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        );
        int capacity = 50;
        
        double answer = fractionalKnapsack(items, capacity);
        if (Math.abs(answer - 240.0) > 1e-9) throw new AssertionError();
    }
}

import heapq

def huffman_coding(frequencies):
    """Return deterministic (symbol, code) pairs.

    Heap construction is O(k log k); walking the finished tree costs O(C),
    where C is the total number of code bits materialized across symbols.
    """
    if any(weight <= 0 for weight in frequencies.values()):
        raise ValueError("frequencies must be positive")
    if not frequencies:
        return []

    # node = (symbol-or-None, left, right). The remaining tuple fields give
    # the heap a total deterministic order without comparing node objects.
    heap = []
    serial = 0
    for symbol, weight in sorted(frequencies.items()):
        heapq.heappush(heap, (weight, symbol, serial, (symbol, None, None)))
        serial += 1

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = (None, left[3], right[3])
        heapq.heappush(
            heap,
            (left[0] + right[0], min(left[1], right[1]), serial, parent),
        )
        serial += 1

    codes = {}
    def visit(node, prefix):
        symbol, left, right = node
        if symbol is not None:
            codes[symbol] = prefix or "0"
            return
        visit(left, prefix + "0")
        visit(right, prefix + "1")

    visit(heap[0][3], "")
    return sorted(codes.items(), key=lambda pair: (len(pair[1]), pair[0]))

freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
codes = huffman_coding(freq)
assert dict(codes)['f'] == '0'
for char, code in codes:
    print(f"{char}: {code}")

import java.util.*;

public class HuffmanCoding {
    static class Node implements Comparable<Node> {
        int freq;
        char ch;
        char minChar;
        Node left, right;
        
        Node(char ch, int freq) {
            this.ch = ch;
            this.minChar = ch;
            this.freq = freq;
        }
        
        Node(int freq, Node left, Node right) {
            this.ch = 0;
            this.minChar = (char) Math.min(left.minChar, right.minChar);
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public int compareTo(Node other) {
            int byFrequency = Integer.compare(this.freq, other.freq);
            return byFrequency != 0 ? byFrequency : Character.compare(this.minChar, other.minChar);
        }
    }
    
    /**
     * Greedy: Always merge two smallest frequencies
     * Builds optimal prefix-free code
     * 
     * Time: O(k log k + C), where C is total emitted code length
     */
    public static Map<Character, String> huffmanCoding(Map<Character, Integer> freq) {
        PriorityQueue<Node> heap = new PriorityQueue<>();
        
        // Create leaf nodes
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            if (entry.getValue() <= 0) throw new IllegalArgumentException("non-positive frequency");
            heap.add(new Node(entry.getKey(), entry.getValue()));
        }
        
        // Build Huffman tree
        while (heap.size() > 1) {
            Node lo = heap.poll();
            Node hi = heap.poll();
            heap.add(new Node(Math.addExact(lo.freq, hi.freq), lo, hi));
        }
        
        // Generate codes
        Map<Character, String> codes = new TreeMap<>();
        generateCodes(heap.peek(), "", codes);
        return codes;
    }
    
    private static void generateCodes(Node node, String code, Map<Character, String> codes) {
        if (node == null) return;
        
        if (node.left == null && node.right == null) {
            codes.put(node.ch, code.isEmpty() ? "0" : code);
            return;
        }
        
        generateCodes(node.left, code + "0", codes);
        generateCodes(node.right, code + "1", codes);
    }
    
    public static void main(String[] args) {
        Map<Character, Integer> freq = new HashMap<>();
        freq.put('a', 5);
        freq.put('b', 9);
        freq.put('c', 12);
        freq.put('d', 13);
        freq.put('e', 16);
        freq.put('f', 45);
        
        Map<Character, String> codes = huffmanCoding(freq);
        codes.forEach((ch, code) -> System.out.println(ch + ": " + code));
        // Greedy merging creates optimal compression!
    }
}