Очередь приоритетов не сортируется

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