модификация в кодировании Хаффмана

Question

Когда я изучал кодирование Хаффмана, я столкнулся с проблемой при работе с приоритетной очередью. Так как я не так хорош в cpp, пожалуйста, помогите.

Вот код

Я попытался внести некоторые изменения, которые я изучил в cpp. В вышеупомянутой программе cpp я изменил нижнюю часть кода

struct Node
{
    char ch;
    int freq;
    Node *left, *right;
};


struct comp
{
    bool operator()(Node* l, Node* r)
    {
        // highest priority item has lowest frequency
        return l->freq > r->freq;
    }

};

и использование его в качестве priority_queue<Node*, vector<Node*>, comp> pq в функции buidingHuffmanTree().

Я изменил его на

struct Node
{
    char ch; 
    int freq;
    Node *left, *right;
    bool operator<(Node const& other) {
    return freq < other.freq;
}
};

Теперь я попытался использовать его как priority_queue<Node*, vector<Node*>> pq

Но я получаю неправильные ответы. В приведенной выше программе вход статический, вы можете видеть, что ответы точно (входной вывод большой, я не могу написать здесь)

Также пытался изменить знаки как freq > other.freq вместо <, получая неправильные ответы

Поскольку оба фрагмента кода работают по-разному, я думал, что они будут работать одинаково.

Answer 1

Проблема в том, что ваша очередь хранит указатели на Node объекты, а не фактические Node сами экземпляры объекта.

Структура comp обрабатывает это с помощью вызова функцииоператор, но перегрузка вашего члена operator< не обрабатывает указатели.

Более конкретно, для перегрузки оператора члена, левая сторона должна быть экземпляром объекта (которым является функция), а не указатель.

---

Если вы не хотите использовать объекты-функторы, но вместо этого хотите использовать перегрузку операторов, вы можете создать функцию, не являющуюся членом, которая принимает два указателя в качестве аргументов:

struct Node
{
    char ch; 
    int freq;
    Node *left, *right;

    // By using `friend` we declare this as a non-member function
    friend bool operator<(Node const* left, Node const* right)
        return left->freq < right->freq;
    }
};