Implementing a priority queue

[adikid89]

I'm trying to implement a priority queue, but I'm having some problems with the dequeue() function. I used a binary tree to implement the queue, so the biggest element is at the rightmost element.

template<class T>
T priority_queue<T>::dequeue()
{
	T data;
	if(root == NULL) {
		cerr << "Nothing in the queue!" << endl;
		exit(1);
	}
	_dequeue(root, data);
	_size--;
	return data;
}
template<class T>
void priority_queue<T>::_dequeue(node*& tree, T& data)
{
	if(tree==NULL) return;
	else {
	_dequeue(tree->right, data);
		{ //found it, now delete it
          /*        Here is the problem,
            If _dequeue makes two recursive calls, when it unwinds
         it comes back here twice, deleting the rightmost element,
         and its parent element...(and so on with more rec. calls.)
          */
			if(tree->left != NULL) {
				node* temp = tree;
				data = tree->data;
				tree = tree->left;
				delete temp;
			} else {
				data = tree->data;
				delete tree;
				tree = NULL;
			}
		}
	}

}

I tried to figure out how to make it. I think I could have a T max variable within the class that would remember the biggest element, so the element that would get deleted, and that would fix the problem, but I'd rather not do so, because it seems like a ugly hack. Any ideas please?

[adikid89]

Okay.. I sort of fixed it, in the sense that the queue works now, but it still looks way too ugly to be the best way of doing this. Basically I just want to get the rightmost value from a binary tree. It sounds soo easy, still I'm at it for a couple of hours. Here is my fix.. Please suggest some better fixes if you have the time.

}
template<class T>
void priority_queue<T>::_dequeue(T& data)
{
	if(root==NULL) return;
	node* pre = root;     //remember the old position of the root node
	while(root->right != NULL) {
		pre = root;
		root = root->right;  //move the root node down the tree to the biggest value
	}//now i've got the biggest element and it's parent
		if(pre != root) {
			//if it doesn't have any childs
			if(root->left == NULL) {
				node* tmp = root;
				data = root->data;
				root = pre;
				root->right = NULL;
				delete tmp;
			} else {
				node* tmp = root;
				data = root->data;
				root = pre;
				root->right = tmp->left;
				delete tmp;
			}
			//if the previous node is the root
		} else {
			data = root->data;
			node* tmp = root;
			root = root->left;
			delete tmp;
		}
}

Nvm.. still not fixed! :| I'll go back on reading.