Priority Queue Not Sorting

Question

Я пытаюсь реализовать собственный алгоритм кодирования Хаффмана и очередь приоритетов для C++ STL, похоже, работает некорректно. Я беру символы из строки и вставляю их в очередь приоритетов по порядку их частоты в строке. Код компилируется и запускается без ошибок, единственное, что дерево, похоже, не сортирует правильно. Вот код,

class Node { 
public: 
    int freq; 
    char data; 
    Node(int &f, char &d) { freq=f; data=d; } 
    bool operator<(const Node* &n) const { return n->freq < this->freq; } 
}; 

void Init(priority_queue<Node*> &tree, string input) { 
map<char,int> probability; 
for(int i=0 ; i<input.size() ; i++) { 
    probability[input[i]]++; 
} 
map<char,int>::iterator it = probability.begin(); 
for(it ; it != probability.end() ; it++) { 
    Node* blah = new Node(it->second, (char&) it->first); 
    tree.push(blah); 
} 

}

что я делаю не так?

Благодаря

Answer 1

Вы хранение указателей в priority_queue, так что элементы сортируются по значению указателя, а не с помощью перегрузки operator<.

Вам нужно либо сохранить Node объектов в очереди приоритетов, либо вам нужно написать пользовательскую функцию сравнения для очереди приоритетов, которая разыгрывает сохраненные указатели и сравнивает объекты Node, на которые они указывают.

Поскольку вы спросите: «Что я делаю неправильно ?,» Вот некоторые другие предложения:

• Ваша перегрузка operator< должна принять константную ссылку, а не ссылка на указатель.
• Ваш конструктор Node должен принимать свои параметры по значению или, по крайней мере, по ссылке const. Литой (char&)it->first не очень хорошо. Пусть const поможет вам написать хороший код, не сражайтесь с ним.
• Возможно, вы должны хранить объекты Node непосредственно в очереди приоритетов, а не указатели.
• Вы используете using namespace std где-нибудь; вы должны удалить это и указать std:: везде, где вам нужно.