Priority Queue Not Sorting

Question

Im trying to implement my own Huffman Coding algorithm and the priority queue for the C++ STL does not seem to be working correctly. I am taking characters from a string and inserting them into a priority queue by order of their frequency in the string. The code compiles and runs without error, the only thing is the tree seems to not be sorting correctly. Here is the code,

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);
 }

}

what am I doing wrong?

Thanks

Answer 1

You are storing pointers in the priority_queue, so the elements are sorted by pointer value, not using your operator< overload.

You either need to store Node objects in the priority queue, or you need to write a custom comparison function for the priority queue that dereferences the stored pointers and compares the Node objects they point to.

Since you ask "what am I doing wrong?," here are some other suggestions:

• Your operator< overload should take a const reference, not a reference to a pointer.
• Your Node constructor should take its parameters by value, or at the very least by const reference. The cast (char&)it->first is not good. Let const help you write good code, don't fight against it.
• You probably should store Node objects directly in the priority queue, not pointers.
• You are using using namespace std somewhere; you should remove this and spell out std:: wherever you need to.