#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

// 霍夫曼樹節(jié)點結構
struct HuffmanNode {
    int weight;          // 節(jié)點權重（字符頻率）
    char data;           // 存儲字符（非葉子節(jié)點可為空）
    HuffmanNode* left;   // 左孩子
    HuffmanNode* right;  // 右孩子

    // 構造函數
    HuffmanNode(int w, char c = '\0') : weight(w), data(c), left(nullptr), right(nullptr) {}
};

// 自定義比較器：最小堆（priority_queue默認最大堆，需反向比較）
struct CompareNode {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight; // 權重小的優(yōu)先出隊
    }
};

// 構建霍夫曼樹
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freq) {
    // 1. 初始化最小堆，將所有字符節(jié)點入堆
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNode> minHeap;
    for (auto& pair : freq) {
        minHeap.push(new HuffmanNode(pair.second, pair.first));
    }

    // 2. 合并節(jié)點，直到堆中只剩1個節(jié)點（根節(jié)點）
    while (minHeap.size() > 1) {
        // 取出兩個權重最小的節(jié)點
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        // 合并為新節(jié)點（權重為兩者之和，數據設為占位符）
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight, '#');
        parent->left = left;
        parent->right = right;

        // 新節(jié)點入堆
        minHeap.push(parent);
    }

    // 堆中剩余節(jié)點即為根節(jié)點
    return minHeap.top();
}

// 計算霍夫曼樹的WPL（遞歸：葉子節(jié)點權重×路徑長度之和）
int calculateWPL(HuffmanNode* root, int depth = 0) {
    if (root == nullptr) return 0;
    // 葉子節(jié)點（無左右孩子）：累加權重×深度
    if (root->left == nullptr && root->right == nullptr) {
        return root->weight * depth;
    }
    // 非葉子節(jié)點：遞歸計算左右子樹WPL之和
    return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}

// 生成霍夫曼編碼（遞歸：左0右1）
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (root == nullptr) return;
    // 葉子節(jié)點：記錄編碼
    if (root->data != '#') {
        codeMap[root->data] = code;
        return;
    }
    // 左分支加0，右分支加1
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 釋放霍夫曼樹內存（避免內存泄漏）
void destroyHuffmanTree(HuffmanNode* root) {
    if (root == nullptr) return;
    destroyHuffmanTree(root->left);
    destroyHuffmanTree(root->right);
    delete root;
}

int main() {
    // 示例：字符頻率（權重）
    unordered_map<char, int> freq = {
        {'A', 5}, {'B', 9}, {'C', 12}, {'D', 13}, {'E', 16}, {'F', 45}
    };

    // 1. 構建霍夫曼樹
    HuffmanNode* root = buildHuffmanTree(freq);

    // 2. 計算WPL（預期輸出224）
    cout << "霍夫曼樹WPL：" << calculateWPL(root) << endl;

    // 3. 生成霍夫曼編碼
    unordered_map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);
    cout << "霍夫曼編碼：" << endl;
    for (auto& pair : codeMap) {
        cout << pair.first << " : " << pair.second << endl;
    }

    // 4. 釋放內存
    destroyHuffmanTree(root);

    return 0;
}

import heapq

def build_huffman_tree(freq):
    """構建霍夫曼樹：返回根節(jié)點（元組形式）"""
    # 1. 初始化最小堆：每個元素是(權重, 字符, 左孩子, 右孩子)
    min_heap = []
    for char, weight in freq.items():
        heapq.heappush(min_heap, (weight, char, None, None))  # 葉子節(jié)點無孩子

    # 2. 合并節(jié)點
    while len(min_heap) > 1:
        # 取出兩個最小權重節(jié)點
        left_weight, left_char, left_left, left_right = heapq.heappop(min_heap)
        right_weight, right_char, right_left, right_right = heapq.heappop(min_heap)

        # 合并為新節(jié)點（權重求和，字符用占位符'#'，孩子為左右節(jié)點）
        parent_weight = left_weight + right_weight
        parent_node = (parent_weight, '#', (left_weight, left_char, left_left, left_right), (right_weight, right_char, right_left, right_right))

        # 新節(jié)點入堆
        heapq.heappush(min_heap, parent_node)

    # 返回根節(jié)點
    return min_heap[0] if min_heap else None

def calculate_wpl(root, depth=0):
    """計算WPL：遞歸遍歷葉子節(jié)點"""
    if root is None:
        return 0
    weight, char, left, right = root
    # 葉子節(jié)點（無左右孩子）
    if left is None and right is None:
        return weight * depth
    # 非葉子節(jié)點：遞歸左右子樹
    return calculate_wpl(left, depth + 1) + calculate_wpl(right, depth + 1)

def generate_huffman_code(root, code="", code_map=None):
    """生成霍夫曼編碼：返回{字符: 編碼}字典"""
    if code_map is None:
        code_map = {}
    if root is None:
        return code_map
    weight, char, left, right = root
    # 葉子節(jié)點：記錄編碼
    if char != '#':
        code_map[char] = code
        return code_map
    # 左0右1遞歸
    generate_huffman_code(left, code + "0", code_map)
    generate_huffman_code(right, code + "1", code_map)
    return code_map

if __name__ == "__main__":
    # 示例：字符頻率
    freq = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}

    # 1. 構建霍夫曼樹
    root = build_huffman_tree(freq)

    # 2. 計算WPL（預期224）
    print(f"霍夫曼樹WPL：{calculate_wpl(root)}")

    # 3. 生成編碼
    code_map = generate_huffman_code(root)
    print("霍夫曼編碼：")
    for char, code in code_map.items():
        print(f"{char} : [code]")

import java.util.*;

// 霍夫曼樹節(jié)點類
class HuffmanNode {
    int weight;   // 權重
    char data;    // 字符（非葉子節(jié)點為'#'）
    HuffmanNode left;  // 左孩子
    HuffmanNode right; // 右孩子

    // 構造函數
    public HuffmanNode(int weight, char data) {
        this.weight = weight;
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// 自定義比較器：按權重升序排序（最小堆）
class NodeComparator implements Comparator<HuffmanNode> {
    @Override
    public int compare(HuffmanNode a, HuffmanNode b) {
        return a.weight - b.weight; // 權重小的優(yōu)先
    }
}

public class HuffmanTreeDemo {
    // 構建霍夫曼樹
    public static HuffmanNode buildHuffmanTree(Map<Character, Integer> freq) {
        // 1. 初始化最小堆
        PriorityQueue<HuffmanNode> minHeap = new PriorityQueue<>(new NodeComparator());
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            minHeap.add(new HuffmanNode(entry.getValue(), entry.getKey()));
        }

        // 2. 合并節(jié)點
        while (minHeap.size() > 1) {
            // 取出兩個最小權重節(jié)點
            HuffmanNode left = minHeap.poll();
            HuffmanNode right = minHeap.poll();

            // 合并為新節(jié)點
            HuffmanNode parent = new HuffmanNode(left.weight + right.weight, '#');
            parent.left = left;
            parent.right = right;

            // 新節(jié)點入堆
            minHeap.add(parent);
        }

        // 返回根節(jié)點
        return minHeap.peek();
    }

    // 計算WPL
    public static int calculateWPL(HuffmanNode root, int depth) {
        if (root == null) return 0;
        // 葉子節(jié)點
        if (root.left == null && root.right == null) {
            return root.weight * depth;
        }
        // 遞歸左右子樹
        return calculateWPL(root.left, depth + 1) + calculateWPL(root.right, depth + 1);
    }

    // 生成霍夫曼編碼
    public static void generateHuffmanCode(HuffmanNode root, String code, Map<Character, String> codeMap) {
        if (root == null) return;
        // 葉子節(jié)點
        if (root.data != '#') {
            codeMap.put(root.data, code);
            return;
        }
        // 左0右1
        generateHuffmanCode(root.left, code + "0", codeMap);
        generateHuffmanCode(root.right, code + "1", codeMap);
    }

    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);

        // 1. 構建霍夫曼樹
        HuffmanNode root = buildHuffmanTree(freq);

        // 2. 計算WPL（預期224）
        System.out.println("霍夫曼樹WPL：" + calculateWPL(root, 0));

        // 3. 生成編碼
        Map<Character, String> codeMap = new HashMap<>();
        generateHuffmanCode(root, "", codeMap);
        System.out.println("霍夫曼編碼：");
        for (Map.Entry<Character, String> entry : codeMap.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}