My Huffman Coding using Two Queues and a Cursor

[fparan]

Hey everybody,

I just want to know what you think of a Huffman coding implemented using two queues and a cursor instead of using a binary tree or a priority. Please feel free to post your thoughts about it or what can be done to improve its performance. Basically, the algorithm has two queues as arguments where it first reads the first one (which has to be sorted BTW),and then creates the second queue by adding the values of the two lowest nodes in the first queue. The cursors serve as pointers of each nodes in the second queue to its left and right children in the first one. I think with the whole process, the algorithm has an O(n) number of operations but you be the critic.

void HuffmanEncoding (Queue& q1, Queue& q2)
{/*
input - an initial sorted queue q1 of the frequencies of each character
output - a sorted list q2 composed where every node is the sum of two elements 
         in q1 and has cursors in each one of these.
*/

QueueNode *leftChild, *rightChild, *tempNode;

q1.enqueue(q1.dequeue());
q2.enqueue(q1.front()+q1.back());
rightChild = q1.backNode();
q1.enqueue(q1.dequeue());
leftChild = q1.backNode();

q2.setCursor(leftChild, rightChild);


while (q1.back() <= q1.front())
{//@pre: q1 has all the elements sorted
//@post: all elements in q1 will be back in place with each of them referenced
//       by elements in q2
	q2.enqueue( q1.front()+q2.front() );
	tempNode = q2.backNode();
	q2.enqueue(q2.dequeue());
	tempNode->rightCursor = q2.backNode();
	
	q1.enqueue(q1.dequeue());
	tempNode->leftCursor = q1.backNode();

	while( q2.frontNode() != tempNode)
		q2.enqueue(q2.dequeue());
	tempNode = NULL;
}

}

/**Queue.h*/

#include "QueueException.h"
typedef int QueueItemType;

struct QueueNode
          {
                 QueueItemType item;
                 QueueNode *leftCursor;
                 QueueNode *rightCursor;
                 QueueNode *next;
          };
          
class Queue
{
public: 
        Queue();
        ~Queue();
        
        bool isEmpty() const;
        QueueItemType front() const throw(QueueException);
        QueueItemType back() const throw(QueueException);
        QueueItemType dequeue() throw(QueueException);
        QueueNode *frontNode() const throw(QueueException);
        QueueNode *backNode() const throw(QueueException);
        
        //void sortQueue(Queue& q)  throw(QueueException);
        void dequeue(QueueItemType& queueFront)       throw(QueueException);
        void enqueue(const QueueItemType& newItem)  throw(QueueException);
        void setCursor(QueueNode *l, QueueNode *r)  throw(QueueException);
        
private:  
          QueueNode *backPtr;
          QueueNode *frontPtr;
};