struct Symbol {

    char ch; //字符

    long long freq; //频率

    string code; //哈夫曼编码

};

struct Node {

    long long w; //权值

    int l, r; //左右孩子（节点下标），-1 表示空

    int sym; // 叶子对应符号下标；内部节点为 -1

    Node(long long _w = 0, int _l = -1, int _r = -1, int _sym = -1)

       : w(_w), l(_l), r(_r), sym(_sym) {}

};

// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标

static int PopMinNode(const vector<Node>& nodes,

    const vector<int>& leafIdx, int n, int& pA,

    const vector<int>& internalIdx, int& pB) {

    if (pA < n && (pB >= (int)internalIdx.size() ||

       nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {

       return leafIdx[pA++];

    }

    else {

       return internalIdx[pB++];

    }

}

// DFS 生成编码（左 0，右 1）

static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {

    if (u == -1) return;

    if (nodes[u].sym != -1) { // 叶子

       sym[nodes[u].sym].code = path;

       return;

    }

    path.push_back('0');

    DFSBuildCodes(nodes[u].l, nodes, sym, path);

    path.pop_back();

    path.push_back('1');

    DFSBuildCodes(nodes[u].r, nodes, sym, path);

    path.pop_back();

}

int BuildHuffmanCodes(Symbol sym[], int n) {

    for (int i = 0; i < n; i++) sym[i].code.clear();

    if (n <= 0) return -1;

    // 只有一个字符：约定编码为 "0"

    if (n == 1) {

       sym[0].code = "0";

       return 0;

    }

    vector<Node> nodes;

    nodes.reserve(2 * n);

    // 1) 建立叶子节点

    vector<int> leafIdx(n);

    for (int i = 0; i < n; i++) {

       leafIdx[i] = (int)nodes.size();

       nodes.push_back(Node(sym[i].freq, -1, -1, i));

    }

    // 2) 叶子按权值排序（A 队列）

    sort(leafIdx.begin(), leafIdx.end(),

       [&](int a, int b) {

           if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;

           return nodes[a].sym < nodes[b].sym; // 稳定一下

       });

    // B 队列（内部节点下标队列）

    vector<int> internalIdx;

    internalIdx.reserve(n);

    int pA = 0, pB = 0;

    // 3) 合并 n-1 次

    for (int k = 1; k < n; k++) {

       int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);

       int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);

       int z = (int)nodes.size();

       ________________________ // 在此处填写代码

    }

    int root = internalIdx.back();

    // 4) DFS 生成编码

    string path;

    DFSBuildCodes(root, nodes, sym, path);

    return root;

}