优先级队列未排序

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<重载应该是一个const引用,而不是对指针的引用.
• 您的Node构造函数应该按值获取其参数,或者至少使用const引用.演员阵容(char&)it->first不好.让const你帮助你写好代码,不要反对它.
• 您可能应该将Node对象直接存储在优先级队列中,而不是指针.
• 你正在using namespace std某个地方使用; 你应该删除它并拼出std::你需要的地方.