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

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

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

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

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

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

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

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

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

// 計(jì)算霍夫曼樹的WPL（遞歸：葉子節(jié)點(diǎn)權(quán)重×路徑長度之和）
int calculateWPL(HuffmanNode* root, int depth = 0) {
    if (root == nullptr) return 0;
    // 葉子節(jié)點(diǎn)（無左右孩子）：累加權(quán)重×深度
    if (root->left == nullptr && root->right == nullptr) {
        return root->weight * depth;
    }
    // 非葉子節(jié)點(diǎn)：遞歸計(jì)算左右子樹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é)點(diǎn)：記錄編碼
    if (root->data != '#') {
        codeMap[root->data] = code;
        return;
    }
    // 左分支加0，右分支加1
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

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

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

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

    // 2. 計(jì)算WPL（預(yù)期輸出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. 釋放內(nèi)存
    destroyHuffmanTree(root);

    return 0;
}

import heapq

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

    # 2. 合并節(jié)點(diǎn)
    while len(min_heap) > 1:
        # 取出兩個(gè)最小權(quán)重節(jié)點(diǎn)
        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é)點(diǎn)（權(quán)重求和，字符用占位符'#'，孩子為左右節(jié)點(diǎn)）
        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é)點(diǎn)入堆
        heapq.heappush(min_heap, parent_node)

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

def calculate_wpl(root, depth=0):
    """計(jì)算WPL：遞歸遍歷葉子節(jié)點(diǎn)"""
    if root is None:
        return 0
    weight, char, left, right = root
    # 葉子節(jié)點(diǎn)（無左右孩子）
    if left is None and right is None:
        return weight * depth
    # 非葉子節(jié)點(diǎn)：遞歸左右子樹
    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é)點(diǎn)：記錄編碼
    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. 構(gòu)建霍夫曼樹
    root = build_huffman_tree(freq)

    # 2. 計(jì)算WPL（預(yù)期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é)點(diǎn)類
class HuffmanNode {
    int weight;   // 權(quán)重
    char data;    // 字符（非葉子節(jié)點(diǎn)為'#'）
    HuffmanNode left;  // 左孩子
    HuffmanNode right; // 右孩子

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

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

public class HuffmanTreeDemo {
    // 構(gòu)建霍夫曼樹
    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é)點(diǎn)
        while (minHeap.size() > 1) {
            // 取出兩個(gè)最小權(quán)重節(jié)點(diǎn)
            HuffmanNode left = minHeap.poll();
            HuffmanNode right = minHeap.poll();

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

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

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

    // 計(jì)算WPL
    public static int calculateWPL(HuffmanNode root, int depth) {
        if (root == null) return 0;
        // 葉子節(jié)點(diǎn)
        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é)點(diǎn)
        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. 構(gòu)建霍夫曼樹
        HuffmanNode root = buildHuffmanTree(freq);

        // 2. 計(jì)算WPL（預(yù)期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());
        }
    }
}