题解 | 荷马史诗

题目链接:洛谷P2168

题干解析:

总体需求: 题目要求我们针对n种不同的单词,使用k进制编码进行编号,使编码后的文本长度最小.

对于任意两个不同的单词,其编码不能有公共前缀.

追加需求: 在确保总长最小的情况下使最长编码尽可能最短.

这是典型的哈夫曼编码压缩的实现,同时需要我们建立的哈夫曼树高度尽可能小.此后此题基本上没有其他限制,模拟实现即可.

算法思路:

由于题目允许k进制编码,传统的二叉哈夫曼树并不完全契合本题情况,以下实现通过模拟k叉树进行实现.

首先建立哈夫曼树过程:

由于k叉哈夫曼树子叶节点数m应满足: (m - 1) mod (k - 1) = 0,即(m - 1)能被k - 1整除(建立的k叉哈夫曼树每个非子叶节点均有k个孩子,总计多出k - 1个节点,其他节点均如此,加之最初的节点,共计m个末端节点(子叶节点),因此(m - 1) % (k - 1) == 0).因此题目给予的节点数可能不够,需要捏造虚拟节点(初始权重为0).然后使用贪心合并,每次选中权重最小的k个节点进行合并,如果权重相等,树高矮矮的优先,抑制树增高(树高与最长编码长度正相关).其中选中k个符合要求的节点可以使用最小堆来完成.

其次分配编码:

通过DFS遍历所有节点分配编码,注意虚拟节点与中间节点不需要记录其编码即可.

实现代码:

以下实现代码更加侧重于生产情况,如果只是写算法题则没必要完全保存所有编码,记录编码长度即可.

#include <bits/stdc++.h>
using namespace std;

template<typename Weight = int>
class KHT {
    struct KHTNode {
        /**
         * 权重(频数)
         */
        Weight weight;
        /**
         * 叶索引(内部节点为-1)
         */
        int idx;
        /**
         * 当前子树高度(辅助减短最长编码)
         */
        int depth;
        /**
         * 子叶节点指针
         */
        vector<shared_ptr<KHTNode> > children;

        KHTNode(Weight _weight, const int _idx, const int _depth) : weight(_weight), idx(_idx), depth(_depth) {
        }
    };

    /**
     * 最小堆比较器
     */
    struct NodeCompare {
        bool operator() (const shared_ptr<KHTNode>& a, const shared_ptr<KHTNode>& b) const {
            if (a->weight != b->weight) return a->weight > b->weight; // 权重小优先
            return a->depth > b->depth; // 深度小优先,抑制树增高
        }
    };

    /**
     * 编码进制-k
     */
    int _k;
    /**
     * 树根节点
     */
    shared_ptr<KHTNode> _root;
    /**
     * 映射表: idx->code
     */
    vector<vector<uint8_t>> _codes;
    /**
     * 最长编码长度
     */
    int max_code;

    /**
     * 根据权重生成树
     *
     * @param weights 权重(频数)数组
     */
    void buildTree(const vector<Weight>& weights) {
        // 补充虚拟节点
        const int n = weights.size();
        int dummy_cnt = (_k - 1) - (n - 1) % (_k - 1);
        if (dummy_cnt == _k - 1) dummy_cnt = 0;

        // 最小堆
        priority_queue<
            shared_ptr<KHTNode>,
            vector<shared_ptr<KHTNode>>,
            NodeCompare
        > minHeap;

        // 添加有权子叶节点
        for (int i = 0; i < n; ++i) minHeap.push(make_shared<KHTNode>(weights[i], i, 0));
        // 添加虚拟节点
        for (int i = 0; i < dummy_cnt; ++i) minHeap.push(make_shared<KHTNode>(Weight(0), -1, 0));

        // 贪心合并
        while (minHeap.size() > 1) {
            auto parent = make_shared<KHTNode>(Weight(0), -1, 0);
            int max_depth = 0;

            for (int i = 0; i < _k; ++i) {
                auto child = minHeap.top();
                minHeap.pop();
                parent->weight += child->weight;
                parent->children.push_back(child);
                max_depth = max(max_depth, child->depth);
            }

            parent->depth = max_depth + 1; // 父节点引出的树高度为子树高度 + 1
            minHeap.push(parent);
        }

        // 标记根节点
        _root = minHeap.top();
    }

    /**
     * DFS分配编码
     *
     * @param node 当前处理节点
     * @param curCode 当前编码
     */
    void generateCodes(shared_ptr<KHTNode>& node, vector<uint8_t>& curCode) {
        // 空节点与虚拟节点直接返回
        if (!node || !node->weight) return;

        // 只有子叶节点压入编码并更新最长编码长度
        if (node->idx != -1) {
            // 压入编码
            _codes[node->idx] = curCode;
            // 更新最长编码长度
            max_code = max(max_code, static_cast<int>(curCode.size()));
            return;
        }

        // 递归访问子节点
        for (int i = 0; i < _k; ++i) {
            // 分配编码: 0,1,2,3...k-1
            curCode.push_back(static_cast<uint8_t>(i));
            generateCodes(node->children[i], curCode);
            curCode.pop_back();
        }
    }

public:
    /**
     * 构造函数
     *
     * @param k 编码进制(树分叉数)
     * @param weights 权重数组
     */
    KHT(const int k, const vector<Weight>& weights) : _k(k), _root(nullptr), _codes(weights.size()), max_code(0) {
        if (k < 2) throw std::invalid_argument("k must be >= 2");
        if (weights.empty()) throw std::invalid_argument("weights cannot be empty");

        // 建树
        buildTree(weights);

        // 生成编码
        vector<uint8_t> code;
        generateCodes(_root, code);
    }

    /**
     * 获取树编码长度*权重总值总和
     *
     * @return 总值
     */
    uint64_t getTotalSize(vector<Weight> weights) const {
        uint64_t sum = 0;
        for (size_t i = 0; i < _codes.size(); ++i) {
            sum += weights[i] * _codes[i].size();
        }
        return sum;
    }

    /**
     * 获取最长编码的长度
     *
     * @return 最长编码长度
     */
    int getMaxCodeSize() const {return max_code;}

    /**
     * 打印编码表(测试用)
     */
    void printCodes() const {
        for (size_t i = 0; i < _codes.size(); ++i) {
            cout << "Idx " << i << ": ";
            for (auto digit : _codes[i]) cout << static_cast<int>(digit);
            cout << ' ' << _codes[i].size();
            cout << endl;
        }
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<uint64_t> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }

    const KHT kht(k, w);
    cout << kht.getTotalSize(w) << endl;
    cout << kht.getMaxCodeSize() << endl;

    // kht.printCodes();
    return 0;
}

复杂度分析:

针对建树过程:

• 每次向堆中插入节点O(log n),共计插入n + C次,时间复杂度为O(nlog n), 空间复杂度为O(n)
• 哈夫曼树总结节点数为(n+dummy_cnt - 1) % (k - 1) 个中间节点,每次取出k个节点,每个节点取出时间复杂度为O(log n),总时间复杂度为O(nklog n)

针对DFS分配编码过程:

• 哈夫曼树总结节点数为(n+dummy_cnt - 1) % (k - 1) + n个节点,每个节点执行一次操作,时间复杂度为O(n)
• 空间复杂度比较复杂n个节点的平均编码空间消耗为O(log n), 总空间消耗为O(nlog n)

因此,时间复杂度建树过程占大头为O(nklog n),空间复杂度分配编码过程占大头,为O(nlog n)