798님의 구현

#include <iostream>

using namespace std;

template <typename T, class Comparator>
class PQueue {
private :
        struct PQueueNode {
                T data;
                PQueueNode* left;
                PQueueNode* right;
                PQueueNode(T value) : data(value), left(NULL), right(NULL) {}
                ~PQueueNode() {
                        if (left!=NULL) {
                                delete left;
                        }
                        if (right!=NULL) {
                                delete right;
                        }
                }
                void enqueue(T value) {
                        Comparator cmp;
                        if (cmp(value, data)>0) {
                                if (right==NULL) {
                                        right=new PQueueNode(data);
                                } else {
                                        if (left==NULL) {
                                                left=right;
                                                right=new PQueueNode(data);
                                        } else {
                                                T temp=right->data;
                                                left->data=right->data;
                                                right->data=data;
                                                left->enqueue(temp);
                                        }
                                }
                                data=value;
                        } else {
                                if (right==NULL) {
                                        right=new PQueueNode(value);
                                } else {
                                        if (left!=NULL) {
                                                if (cmp(value, left->data)>0) {
                                                        right->enqueue(value);
                                                } else {
                                                        left->enqueue(value);
                                                }
                                        } else {
                                                right->enqueue(value);
                                        }
                                }
                        }
                }
                bool dequeue() {
                        if (right!=NULL) {
                                data=right->data;
                                if (right->dequeue()==true) {
                                        if (left!=NULL) {
                                                right->data=left->data;
                                                if (left->dequeue()==true) {
                                                        delete left;
                                                        left=NULL;
                                                }
                                        } else {
                                                delete right;
                                                right=NULL;
                                        }
                                }
                                return false;
                        }
                        return true;
                }
        };
        PQueueNode* root;
public :
        PQueue() : root(NULL) {}
        ~PQueue() {
                if (root!=NULL) {
                        delete root;
                }
        }
        bool isEmpty() {
                return (root==NULL);
        }
        void enqueue(T value) {
                if (root==NULL) {
                        root=new PQueueNode(value);
                } else {
                        root->enqueue(value);
                }
        }
        T dequeue() {
                // assuming root is not null
                T result=root->data;
                if (root->dequeue()==true) {
                        delete root;
                        root=NULL;
                }
                return result;
        }
};


struct IntComparator {
        int operator () (int& left, int& right) {
                if (left>right) {
                        return 1;
                } else if (left==right) {
                        return 0;
                }
                return -1;
        }
};

int main(int argc, char** argv) {
        PQueue<int, IntComparator> queue;

        srand(time(NULL));

        int temp;
        for (int i=0;i<10;++i) {
                temp=rand();
                queue.enqueue(temp);
                cout<<\"Enqueue \"<<temp<<endl;
        }

        while (!queue.isEmpty()) {
                temp=queue.dequeue();
                cout<<\"Dequeue \"<<temp<<endl;
        }
}