You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

  详见实验指导书

  TreeNode结构体如下

struct TreeNode {
    char symbol; // 编码的字母
    double freq; // 对应的频率
    TreeNode *left; // 左孩子
    TreeNode *right; // 右孩子
    // 构造函数
    TreeNode()
        : symbol('\0'), freq(0), left(NULL), right(NULL) {}
    // 用symbol和freq构造 TreeNode 对象
    TreeNode(char symbol_, double freq_)
        : symbol(symbol_), freq(freq_), left(NULL), right(NULL) {}
    // () 函数，用于规定优先队列比较运算
    bool operator () (const TreeNode* lhs, const TreeNode* rhs) {
        return lhs->freq > rhs->freq;
    }
};

Format

  不需要也不要进行输入输出。你所提交的代码应具有如下形式。Huffman树可能有多种不同的构造形式，但总代价应相同。只要你的程序构造出总代价最小的Huffman树，即可通过。

#include "Solution.h"

TreeNode* huffman(vector<TreeNode*>& tree) {
    int n = tree.size();
    // 创建一个小顶堆
    priority_queue<TreeNode*, vector<TreeNode*>, TreeNode> q;
    // 把 tree 放入 q 中
    for (int i = 0; i < n; i++) {
        q.push(tree[i]);
    }

    // 请注意，非叶子结点的 symbol 不需要赋值
    // 请在这里完成你的代码

    return q.top();
}

Samples

  你的程序 不需要输入输出，提供一组样例用于自测

algorithm
17 19 20 5 9 34 78 45 12

670