C++实现哈夫曼算法时结构体插入小顶堆priority_queue报错C2676

你遇到的Error C2676错误由以下几个问题共同导致：

• 默认的priority_queue<node>是大顶堆，底层使用std::less<node>作为比较器，要求node类型提供**const修饰的operator<**重载，你当前只实现了非const的operator>，完全不匹配默认比较器的调用要求。
• 你实现的operator>没有添加const限定符，标准库操作堆内元素时会通过const引用传递对象，非const成员函数无法被const对象调用，直接触发“const类型对象找不到对应运算符”的报错。
• 额外逻辑错误：你写的operator>比较逻辑是反的，就算正确重载也无法得到按频率升序排列的小顶堆。
• 代码规范问题：构造函数里给char类型的c赋值NULL是错误用法，NULL是指针空值常量，char是值类型，应该初始化为'\0'或0。

1. 修改node结构体，删除错误的operator>，添加const修饰的operator<重载，适配小顶堆的排序要求：

struct node
{
    char c; // 存储字符
    int f; // 存储字符频率
    node* next;
    node* left, * right; // 哈夫曼树左右子节点

    node()
    {
        f = 0;
        left = NULL;
        right = NULL;
        c = '\0';
        next = NULL;    
    }

    // const修饰的<运算符重载，供priority_queue调用
    bool operator<(const node& a) const
    {
        // 返回true代表当前节点优先级低于传入节点，会被放到堆的下层
        // 小顶堆要求频率小的优先级高，因此当前节点频率大于传入节点时返回true
        return f > a.f;
    }
};

修改完成后你原来的priority_queue <node> pq;不需要额外调整，就会自动成为按频率从小到大排序的小顶堆，符合哈夫曼树构建的需求。

2. （可选优化）替换你当前两层循环的频率统计逻辑，原来的实现时间复杂度高，还可能出现重复入堆的问题，用长度256的频率数组一次遍历就能完成统计：

void CharacterFrequency()
{
    int freq[256] = {0};
    // 一次遍历统计所有字符出现次数
    for (char ch : text)
    {
        freq[(unsigned char)ch]++;
    }
    // 将所有出现过的字符入堆
    for (int i = 0; i < 256; i++)
    {
        if (freq[i] > 0)
        {
            PriorityQueue((char)i, freq[i]);
        }
    }
}

修改完成后重新编译即可消除报错，堆内元素会按照频率从小到大排序，每次top()取到的都是当前频率最低的节点，满足哈夫曼编码的构建要求。

内容的提问来源于stack exchange，提问作者Muhammad Taimoor