C++实现哈夫曼编码时自定义优先队列的关系运算符重载失效问题求助

嘿，我仔细看了你的代码，核心问题一下子就找到了：你重载的是Node对象的operator<和operator>，但实际操作的是Node*指针——C++里默认会直接比较指针的内存地址，根本不会调用你定义的基于value的比较逻辑！

比如你在带trigger的Insert函数里写的if(v[parent] > v[node])，这里v[parent]和v[node]都是Node*类型，编译器会用内置的指针地址比较，完全忽略你写的对象运算符，所以你的条件永远不会按预期触发。

下面给你几种可行的解决方案，按推荐程度排序：

方案1：使用自定义比较器（最推荐，符合C++惯例） #

不要在Node结构体里重载运算符，而是专门写一个用于比较Node*的函数对象，让你的Priority_Queue用这个比较器来判断元素优先级。

步骤1：定义比较器结构体 #

// 小顶堆比较器：值大的元素应该排在后面，所以返回a的value > b的value
struct NodeMinComparator {
    bool operator()(const Node* a, const Node* b) {
        return a->value > b->value;
    }
};

// 大顶堆比较器：值小的元素应该排在后面，返回a的value < b的value
struct NodeMaxComparator {
    bool operator()(const Node* a, const Node* b) {
        return a->value < b->value;
    }
};

步骤2：修改Priority_Queue模板，支持比较器 #

把你的Priority_Queue改成接受比较器作为模板参数，然后在堆操作里用比较器代替直接的>/<：

template <class T, class Comparator = NodeMaxComparator>
class Priority_Queue{
public:
    int k;
    int sz;
    vector<T> v;
    Comparator comp; // 比较器实例

    Priority_Queue(int k) : k(k), sz(0) {}

    void heapify(int index,int n){
        int target_index = index;
        for(int i = index*k+1;i <= min(n-1,index*k+k);++i){
            // 用比较器判断：如果当前target的元素应该排在i元素后面，就更新target
            if(comp(v[target_index], v[i])){
                target_index = i;
            }
        }
        if(index != target_index){
            swap(v[target_index],v[index]);
            heapify(target_index,n);
        }
    }

    void Insert(T val){
        if(sz == (int)v.size()){
            v.push_back(val);
            ++sz;
        } else {
            v[sz++] = val;
        }
        int node = sz-1;
        while(node >= 1){
            int parent = (node-1)/k;
            // 用比较器判断是否需要交换父节点和当前节点
            if(comp(v[parent], v[node])){
                swap(v[parent],v[node]);
                node = parent;
            } else {
                break;
            }
        }
    }

    // 其他函数（Pop、Top、printHeap）可以保持不变，或者根据比较器调整逻辑
    void Pop(){
        if(sz == 0){
            cout << "Heap Underflow\n";
            return;
        }
        swap(v[0],v[sz-1]);
        --sz;
        heapify(0,sz);
    }

    T Top(){
        return v[0];
    }

    void printHeap(){
        for(int i = 0; i < sz;++i){
            cout << v[i]->value << " ";
        }
        cout << "\n";
    }
};

步骤3：实例化对应类型的优先队列 #

在main里创建小顶堆时，指定NodeMinComparator即可：

int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> freq(26,0);
    for(int i = 0; i < n;++i){
        ++freq[s[i]-'a'];
    }
    // 实例化小顶堆，用NodeMinComparator
    Priority_Queue<Node*, NodeMinComparator> pq(2);
    for(int i = 0; i < 26;++i){
        if(freq[i] == 0) continue;
        pq.Insert(new Node(char(i+'a'),freq[i],NULL,NULL));
    }
    pq.printHeap(); // 输入"aab"的话，会输出1 2，符合小顶堆预期
}

方案2：重载针对Node*的全局运算符（不推荐） #

你可以直接重载全局的operator>和operator<来处理Node*类型，但这种方法容易引发意外——全局的指针运算符重载会影响所有Node*的比较，可能在代码其他地方导致非预期行为：

// 全局重载指针比较运算符
bool operator>(const Node* a, const Node* b) {
    return a->value > b->value;
}

bool operator<(const Node* a, const Node* b) {
    return a->value < b->value;
}

这种方法虽然能解决当前问题，但不建议在实际项目中使用，会破坏代码的可读性和安全性。

方案3：存储Node对象而非指针（不适合哈夫曼场景） #

如果你把Priority_Queue<Node*>改成Priority_Queue<Node>，那么你之前重载的对象运算符就会生效，但哈夫曼编码需要不断合并节点、动态创建新节点，存储对象会涉及频繁拷贝，效率低且容易出错，所以这个方案不适合你的场景。

额外的代码小问题修正 #

你的heapify函数还有一个编译错误：第一个heapify里递归调用heapify(v,max_index,n);，但函数参数是int index,int n，多传了v参数，需要改成heapify(max_index,n);。

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