Priority Queue implementation using binary searching trees: Minimum priority items can be found at the leftmost leaf, maximum priority items at the rightmost one. Should have insertion/lookup complexities of around `log n`.

PriorityTreeQueue.cpp

/*

Compile this file using a C++11-compliant compiler!

*/

# include <iostream>
# include <string>
# include <vector>

using std::vector;
using std::string;

template<typename T, typename Prio = int>
struct prioq_node
{
    typedef prioq_node<T,Prio> node_type;

    T data;
    Prio priority;
    node_type *left, *right;
    bool initialized = false;

    prioq_node(const T& el, Prio p) : data(el), priority(p), initialized(true) {};
    void insert(const T&, Prio);
};

template<typename T, typename Prio>
void prioq_node<T,Prio>::insert(const T& el, Prio p)
{
    if ( ! initialized )
    {
        data = el;
        priority = p;
        initialized = true;
    } else if ( p > priority )
    {
        if ( right == nullptr )
            right = new prioq_node<T,Prio>(el,p);
        else
            right->insert(el,p);
    } else if ( p <= priority )
    {
        if ( left == nullptr )
            left = new prioq_node<T,Prio>(el,p);
        else
            left->insert(el,p);
    } else
    {
        throw "This shouldn't have happened";
    }
}

/*******************/

template<typename T, typename Prio = int>
struct prioq
{
    typedef prioq_node<T,Prio> node_type;
    node_type* root;

    prioq(void) : root(nullptr) {};
    void insert(const T&, Prio);
    T get_max(void);
    T get_min(void);
};

template<typename T, typename Prio>
void prioq<T,Prio>::insert(const T& el, Prio p)
{
    if ( root == nullptr )
        root = new prioq_node<T,Prio>(el,p);
    else
        root->insert(el,p);
}

template<typename T, typename Prio>
T prioq<T,Prio>::get_max(void)
{

    if ( root == nullptr )
    {
        throw "Empty queue!";
    } else if ( root->right )
    {
        node_type* current_node = root;
        node_type* parent_node = nullptr;

        while ( current_node->right ) // Go as far to the right as we can go.
        {
            parent_node = current_node;
            current_node = current_node->right;
        }

        T return_value = current_node->data;

        node_type* to_delete = current_node;
        parent_node->right = nullptr;
        
        if ( current_node->left )
            parent_node->right = current_node->left;

        delete to_delete;
        return return_value;
    } else if ( root->left ) // Only left child exists: Return root's data and set the left child as new root.
    {
        T return_value = root->data;
        node_type* to_delete = root;
        root = root->left;
        delete to_delete;
        return return_value;
    } else if ( !root->right && !root->left ) // Root has no children at all: Return root's data and delete root.
    {
        T return_value = root->data;
        delete root;
        root = nullptr;
        return return_value;
    } else
        throw "Shouldn't have happened: Last else in prioq::get_max";
}

template<typename T, typename Prio>
T prioq<T,Prio>::get_min(void)
{
    if ( root == nullptr )
    {
        throw "Empty queue!";
    } else if ( root->left )
    {
        node_type* current_node = root;
        node_type* parent_node = nullptr;

        while ( current_node->left )
        {
            parent_node = current_node;
            current_node = current_node->left;
        }

        T return_value = current_node->data;

        node_type* to_delete = current_node;
        parent_node->left = nullptr;

        if ( current_node->right )
            parent_node->left = current_node->right;

        delete to_delete;
        return return_value;
    } else if ( root->right )
    {
        T return_value = root->data;
        node_type* to_delete = root;

        root = root->right;

        delete to_delete;
        return return_value;

    } else if ( !root->right && !root->left )
    {
        T return_value = root->data;
        delete root;
        root = nullptr;
        return return_value;
    } else
        throw "Shouldn't have happened: Last else in get_min";
}

int main(void)
{
    prioq<int> p;

    vector<int> v{74,6,29,75,1,1,1,278,27,14,15,45,2,4,11,5,84,28,1,3,25,43,76,56,98};

    try {
        for ( int i: v )
            p.insert(i,i);
        while (1)
        {
            int j = p.get_min();
            std::cout << j << std::endl;
        }
    } catch ( const char* s )
    {
        std::cout << s;
    }

    return 0;
}