relational operator overloading not working in C++

Question

I am trying to implement Huffman encoding in C++ using custom made priority_queue. I am storing the information in structure named Node. Here is the code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//two same name functions are for min heap and max heap(Function overloading)
struct Node{
    char letter;
    int value;
    Node* left;
    Node* right;
    Node(char letter,int value, Node* left,Node* right){
        this->letter = letter;
        this->value = value;
        this->left = left;
        this->right = right;
    }

    bool operator < (const Node* &a){//HERE IS THE PROBLEM
        if((this->value) < (a->value))
            return true;
        else
            return false;
    }

    bool operator > (const Node* &a){//HERE IS THE PROBLEM
        if((this->value) > (a->value))
            return true;
        else
            return false;
    }
};

template <class T>
class Priority_Queue{

    public:
    int k;
    int sz;
    vector<T> v;

    Priority_Queue(int k){
        sz = 0;
        this->k = k;
    }

    void heapify(int index,int n){
        int max_index = index;
        for(int i = index*k+1;i <= min(n-1,index*k+k);++i){
            if(v[i] > v[max_index])
                max_index = i;
        }
        if(index != max_index){
            swap(v[max_index],v[index]);
            heapify(v,max_index,n);
        }
    }

    void heapify(vector<int> &v,int index,int n,bool trigger){
        //for calling min_heapify using function overloading
        int min_index = index;
        for(int i = index*k+1;i <= min(n-1,index*k+k);++i){
            if(v[i] < v[min_index])
                min_index = i;
        }
        if(index != min_index){
            swap(v[min_index],v[index]);
            heapify(v,min_index,n,trigger);
        }
    }   

    void Insert(T val){
        if(sz == (int)v.size()){
            v.push_back(val);
            ++sz;
        }
        else
            v[sz++] = val;
        int parent = (sz-1)/k;
        int node = sz-1;
        while(node >= 1){
            int parent = (node-1)/k;
            if(v[parent] < v[node]){
                swap(v[parent],v[node]);
                node = parent;
                parent = (parent-1)/k;
            }
            else
                break;
        }
    }

    void Insert(T val, bool trigger){
        if(sz == (int)v.size()){
            v.push_back(val);
            ++sz;
        }
        else
            v[sz++] = val;
        int parent = (sz-1)/k;
        int node = sz-1;
        while(node >= 1){
            int parent = (node-1)/k;
            if(v[parent] > v[node]){// IF CONDITION DOESN'T WORK
                swap(v[parent],v[node]);
                node = parent;
                parent = (parent-1)/k;
            }
            else
                break;
        }
    }

    void Pop(){
    if(sz == 0){
            cout << "Heap Underflow\n";
            return;
        }
        swap(v[0],v[sz-1]);
        --sz;
        heapify(0,sz);

    }

    void Pop(bool trigger){
        if(sz == 0){
            cout << "Heap Underflow\n";
            return;
        }
        swap(v[0],v[sz-1]);
        --sz;
        heapify(0,sz,trigger);
    }

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

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

};

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'];
    }
    Priority_Queue<Node*> 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),true);
    }
    pq.printHeap();
}

I don't have much experience with C++ and I am having trouble overloading relational operators where I want to compare two structure pointers based on the value parameter.For example: if I enter aab , the if condition in Insert function should be executed but it never happens. I searched up a lot regarding overloading of relational operators but none of them seem to fix the issue I am facing. Can someone please help me ? What am I doing wrong while overloading the operator?

Answer 1

You probably should make your method look like this:

bool operator<(const Node &node) const {
   return value < node.value;
}

Notice the slightly different method signature. And then you should test it with an absolutely minimal method.

int main(int, char **) {
     Node first{'a', 10, nullptr, nullptr};
     Node second{'b', 5, nullptr, nullptr};

     cout << "first < second: " << (first < second) << endl;
     cout << "second < first: " << (second < first) << endl;
}

In your code, you might have to do this:

if (*v[index] < *v[otherIndex)

Another comment: don't name variables like v. That's going to bite you in the backside as your programs get bigger. Give them longer names that are more searchable and descriptive. vec is better than v.