Using C ++ to implement Hawman Algorithm

I think each computer professional student is more or less to get into the old problem in Hawman code, and the data structure. It is generally given some characters, and the frequency of these characters, let you design a binary code for these characters, requiring the shortest code of the highest frequency. The solution is to construct a Hawman tree (binary tree), its basic idea is that each time you pick up two frequencies from these characters, then construct a new node, make the new node's left and right kid pointers Point to the two nodes, respectively. I think this everyone is very clear, I will not say much. It mainly shows the problem that I have encountered in C . First of all, I defined a javan tree node:

Class Hnode {public: Friend Bool Operator> (Hnode N1, Hnode N2); // Defining a greater than symbols for priority queues using Hnode (String D = ", INT i = 0, Hnode * L = null, hnode * R = NULL): Left (L), Right (R), DATA (D), Value (i) {} hnode * left; hnode * right; string data; // stored string int value; // string Number of times of occurrence};

Bool Operator> (Hnode N1, Hnode N2) {return n1.value> n2.value;

Because only the small homework in the course, I am also not prepared for Hnode definition of the complete binary tree operation, just to store the data object, so there is only one constructor, and all Data Member is public.

This algorithm will encounter a big trouble, mainly because it uses the std :: priority_queue container. At that time, considering the minimum of two frequencies in Haxman (ie, the number of times the number of times, the Value in my hnode is the number of times), and it is natural to think of the std :: priority_queue container, priority queue each time Elements that populate the highest weight in the queue, this feature is undoubtedly the best choice for the Havman algorithm. However, because of the first time with the std :: priority_queue container, the result has a lot of problems, and finally solved in the last one, and also learned a lot.

Preliminary imagination is this, first press all Hnode objects into the priority queue, then pop up two, form a new node, press the new node into the queue, repeat this step, When there is only one element in the queue, the Hawman tree is completed. Like this: (wrong, don't learn)

While (...) {std :: priority_queue q; ..... hnode h1 = q.top (); q.pop (); hnode h2 = q.top (); q.pop () Hnode R; R.L.Light = H2; R.Value = H1.Value H2.Value; q.push (r);}

The first question encountered is that the insertion of all containers of STL is based on by value semantic, that is, to generate a copy of an object is placed in a container. Such consequences are Hnode's Left, and the Right pointer refers to not knowing where it goes. Everyone can draw a few times a few times, I know what is wrong. After considering it, it was found that there would be no such problem if the team's pointer is stored, so it is rewritten:

Hnode * maketree (priority_queue pq) {hnode * p1 = null; hnode * p2 = null; hnode * r = null; while (! pq.empty ()) {p1 = pq.top (); pq. POP (); if (pq.empty ()) {r = p1; return r;} p2 = pq.top (); pq.pop (); r = new hnode; r-> left = p1; r-> Right = p2; r-> value = p1-> value p2-> value; pq.push (r);} return null;} It is immediately encountered. Std :: priority_queue When it is judged priority, the point directly compares the address of the pointer, not the size of the object pointing to the object. The pointer is not a class, I can't rewrite the comparison operation of the pointer. The program has fallen into a dilemma. Std :: Priority_Queue Default Using the Greater <> template to generate a Function Object to compare the element, I tried to write a Hnode * version of the transcription of the Hnode *, but no success. When the mountain heavy water repeated, suddenly, why didn't you write a Function Object to a Function Object to replace Greater <>? Hurry and write down the following code:

Struct PhnodeComp {BOOL Operator () (const hnode * & left, const hnode * & right) const {return left-> value> right-> value;}};

Then turn the std :: priority_queue to the declaration of:

Priority_queue , phnodecomp> pq;

I finally solved this problem. It seems that the knowledge that only gets only from the book is unresolved, and it must be practiced to practice.