The implementation code of max-priority queue and min-priority queue in C++

template<class T> 
class chanMaxPriorityQueue
{
#define ALL_HEAP_SIZE 10001
public:
    chanMaxPriorityQueue() { }

    T heap_maximum()
    {
        return storage[1];
    }

    T heap_extract_max()
    {
        if (heap_size < 1)
            throw runtime_error("there is no heap data to be extracted");

        T max = storage[1];
        storage[1] = storage[heap_size];
        --heap_size;
        max_heapify(1);
        return max;
    }

    void heap_increase_key(int index, const T& key)
    {
        if (key < storage[index])
            throw runtime_error("the input key is smaller than original key");

        storage[index] = key;
        while (index > 1 && storage[Parent(index)] < storage[index])
        {
            T temp = storage[index];
            storage[index] = storage[Parent(index)];
            storage[Parent(index)] = temp;
            index = Parent(index);
        }
    }

    void max_heap_insert(const T& key, const T& minus_max)
    {
        ++heap_size;
        storage[heap_size] = minus_max;
        heap_increase_key(heap_size, key);
    }

    void build_max_heap(const vector<T>& A)
    {
        heap_size = A.size();
        if (heap_size >= ALL_HEAP_SIZE)
            throw runtime_error("the input array is larger than ALL_HEAP_SIZE");

        for (int i = 0; i < heap_size; ++i)
            storage[i + 1] = A[i];

        for (int i = heap_size / 2; i >= 1; --i)
            max_heapify(i);
    }

    void heap_sort(const vector<T>& A)
    {
        build_max_heap(A);
        for (int i = A.size(); i >= 2; --i)
        {
            T temp = storage[i];
            storage[i] = storage[1];
            storage[1] = temp;
            --heap_size;
            max_heapify(1);
        }
    }

    int heap_size = 0;
private:
    T storage[ALL_HEAP_SIZE];
    
    void max_heapify(int index)
    {
        int l = Left(index);
        int r = Right(index);
        int largest = index;

        if (l <= heap_size && storage[l] > storage[index])
            largest = l;

        if (r <= heap_size && storage[r] > storage[largest])
            largest = r;

        if (largest != index)
        {
            T temp = storage[index];
            storage[index] = storage[largest];
            storage[largest] = temp;
            max_heapify(largest);
        }
    }

    inline int Parent(int i) { return (i >> 1); }
    inline int Left(int i) { return (i << 1); }
    inline int Right(int i) { return (i << 1) + 1; }
};

template<class T>
class chanMinPriorityQueue
{
#define ALL_HEAP_SIZE 10001
public:
    chanMinPriorityQueue() { }

    T heap_minimum()
    {
        return storage[1];
    }

    T heap_extract_min()
    {
        if (heap_size < 1)
            throw runtime_error("there is no heap data to be extracted");

        T min = storage[1];
        storage[1] = storage[heap_size];
        --heap_size;
        min_heapify(1);
        return min;
    }

    void heap_decrease_key(int index, const T& key)
    {
        if (key > storage[index])
            throw runtime_error("the input key is larger than original key");
            
        storage[index] = key;
        while (index > 1 && storage[Parent(index)] > storage[index])
        {
            T temp = storage[index];
            storage[index] = storage[Parent(index)];
            storage[Parent(index)] = temp;
            index = Parent(index);
        }
    }

    void min_heap_insert(const T& key, const T& plus_max)
    {
        ++heap_size;
        storage[heap_size] = plus_max;
        heap_decrease_key(heap_size, key);
    }

    void build_min_heap(const vector<T>& A)
    {
        heap_size = A.size();
        if (heap_size >= ALL_HEAP_SIZE)
            throw runtime_error("the input array is larger than ALL_HEAP_SIZE");

        for (int i = 0; i < heap_size; ++i)
            storage[i + 1] = A[i];

        for (int i = heap_size / 2; i >= 1; --i)
            min_heapify(i);
    }

    void heap_sort(const vector<T>& A)
    {
        build_max_heap(A);
        for (int i = A.size(); i >= 2; --i)
        {
            T temp = storage[i];
            storage[i] = storage[1];
            storage[1] = temp;
            --heap_size;
            min_heapify(1);
        }
    }

    int heap_size = 0;
private:
    T storage[ALL_HEAP_SIZE];

    void min_heapify(int index)
    {
        int l = Left(index);
        int r = Right(index);
        int smallest = index;

        if (l <= heap_size && storage[l] < storage[index])
            smallest = l;

        if (r <= heap_size && storage[r] < storage[smallest])
            smallest = r;

        if (smallest != index)
        {
            T temp = storage[index];
            storage[index] = storage[smallest];
            storage[smallest] = temp;
            min_heapify(smallest);
        }
    }

    inline int Parent(int i) { return (i >> 1); }
    inline int Left(int i) { return (i << 1); }
    inline int Right(int i) { return (i << 1) + 1; }
};