算法设计贪心算法实现哈夫曼树c++

贪心算法是一种启发式的问题解决方法，它通过每一步选择当前看起来最优的选择，希望最终得到全局最优解。在构建哈夫曼树（Huffman Tree）这个问题中，我们可以使用贪心算法来实现。哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩。

以下是使用贪心策略（优先队列+贪心合并）在C++中实现哈夫曼树的一个简单步骤：

1. **创建一个字符及其频率的优先队列**：通常是一个最小堆结构，元素按照频率从低到高排序。

2. **循环直到只剩下一个节点**：每次取出堆顶两个频率最低的节点，将它们合并成一个新的节点，新节点的频率等于这两个节点的频率之和，并将新节点插入堆中。

3. **返回堆顶的节点作为根节点**：堆顶的节点就是哈夫曼树的根，因为它经历了最多的次级合并，所以路径长度最短。

4. **构造编码表**：遍历哈夫曼树，从叶子节点开始，记录每个节点到达根节点的路径，路径上遇到0则左移一位，遇到1则右移一位，这样可以得到每个字符的编码。

#include <queue>
#include <vector>

struct Node {
    char data;
    int freq;
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* buildHuffmanTree(std::map<char, int>& freqs) {
    // 创建一个优先队列存储节点
    std::priority_queue<std::pair<int, Node*>, std::vector<std::pair<int, Node*>>, std::greater<std::pair<int, Node*>>> pq(freqs.begin(), freqs.end());
    
    while (pq.size() > 1) {
        int firstFreq = pq.top().first;
        pq.pop();
        int secondFreq = pq.top().first;
        pq.pop();

        // 创建新的节点并入队
        Node* newNode = new Node();
        newNode->freq = firstFreq + secondFreq;
        newNode->left = pq.top().second;
        newNode->right = pq.top().second;
        pq.pop(); // 移除剩下的那个节点

        newNode->left->parent = newNode;
        newNode->right->parent = newNode;

        pq.push({newNode->freq, newNode});
    }

    return pq.top().second; // 返回树的根节点
}