//
// Created by yz on 19-8-31.
//
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/*****************优先队列实现**************************/
//默认仿函数，最大堆
template <class T>
class _compare
{
public:
    bool operator()(T a,T b)
    {
        return a<b;
    }
};

template <class T,class compareType=_compare<T>>
class MyPriorityQueue
{
private:
    T* m_data;//数据
    size_t  m_size;//元素个数
    size_t m_capacity;//队容量
    compareType m_compare;
private:
    void heapInsert();//向上调整堆
    void heapify();//向下调整堆
    void obj_cpy(T*,const T*,size_t);//元素复制
    inline void swap(size_t i,size_t j);//交换元素
public:
    MyPriorityQueue();//构造函数
    ~MyPriorityQueue();

    bool push(const T& obj);//入队操作
    bool pop();//删除队头元素
    T  top();//获取队头元素

    bool empty()const//返回是否为空
    {
        return 0==m_size;
    }
    size_t size()const//返回队列大小
    {
        return m_size;
    }
    size_t capacity()const //返回队列容量
    {
        return m_capacity;
    }
    void show()
    {
        cout<<"队列元素数量为："<<m_size<<endl;
        cout<<"将队列从大到小打印"<<endl;
        size_t len=m_size;
        for (int i = 0; i <len; ++i) {
            cout<<top()<<" ";
            pop();
        }
        cout<<endl;
    }
};
//无参构造函数
template <class T,class compareType>
MyPriorityQueue<T,compareType>::MyPriorityQueue() :m_size(0),m_capacity(10)
{
    m_data=new T[m_capacity];
    if(nullptr==m_data)
    {
        throw "申请空间失败";
    }
}
//析构函数
template <class T,class T2>
MyPriorityQueue<T,T2>::~MyPriorityQueue()
{
    if(m_data!= nullptr)
    {
        delete [] m_data;//释放空间
        m_data= nullptr;//置空
    }
}
//交换元素
template <class T,class T2>
void MyPriorityQueue<T,T2>::swap(size_t i, size_t j)
{
    T temp=m_data[i];
    m_data[i]=m_data[j];
    m_data[j]=temp;
}
//插入队尾后，需要向上重新调整堆结构
template <class T,class T2>
void MyPriorityQueue<T,T2>::heapInsert()
{
    size_t index=m_size-1;//index指向最后一个元素
    //同父节点进行比较，如果满足，交换，上浮
    while(index>0&&m_compare(m_data[(index-1)/2],m_data[index]))
    {
        swap((index-1)/2,index);
        index=(index-1)/2;//index指向他的父节点;
    }
}
//当队头出队，需要将队尾移动到队头，向下重新调整堆
template <class T,class T2>
void MyPriorityQueue<T,T2>::heapify()
{
    size_t index=0;
    size_t left=index*2+1;
    while(left<m_size)//该节点有左孩子
    {
        //有右孩子的话选择左右孩子较大的那一个
        size_t largest=left+1<m_size&&m_compare(m_data[left],m_data[left+1])?left+1:left;
        //比较孩子节点与父节点
        largest=m_compare(m_data[largest],m_data[index])?index:largest;
        if(largest==index)//父节点已经是最大节点跳出循环
        {
            break;
        }
        swap(largest,index);
        index=largest;
        left=2*index+1;
    }

}
//元素复制
template <class T,class T2>
void MyPriorityQueue<T,T2>::obj_cpy(T * dest, const T * sour, size_t n)
{
    for (size_t i = 0; i <n; ++i) {
        dest[i]=sour[i];
    }
}

//入队操作
template <class T,class T2>
bool MyPriorityQueue<T,T2>::push(const T& obj)
{
    T* tempPtr=m_data;
    if(m_size==m_capacity)//空间不足，则需要重新申请空间
    {
        m_capacity*=2;//重新申请的空间的大小
        m_data=new T[m_capacity];
        if(m_data== nullptr)
        {
            m_data=tempPtr;//恢复原来的空间
            m_capacity/=2;//恢复原来的容量
            return false;//返回失败
        }//申请空间成功
        obj_cpy(m_data,tempPtr,m_size);//复制数据到新空间中
        delete [] tempPtr;//删除旧空间
    }
    m_data[m_size++]=obj;//加入队列
    heapInsert();//向上重新调整堆
    return true;
}
//出队操作
template <class T,class T2>
bool MyPriorityQueue<T,T2>::pop()
{
    if(m_size==0)
        return false;
    if (m_size==1)
    {
        m_size=0;
        return true;
    }
    m_data[0]=m_data[m_size-1];//将队尾数据复制到队头
    m_size--;//队尾元素个数减一
    heapify();//重新向下调整堆
    return true;
}
//取队头元素
template <class T,class T2>
T  MyPriorityQueue<T,T2>::top()
{
    if(m_size<=0)
        throw "空队列";
    return m_data[0];//返回队头元素
}
/******************************************************/
//仿函数，最小堆
template <class T>
class MyCompare
{
public:
    bool operator()(T a,T b)
    {
        return a>b;
    }
};
void test01()
{
    MyPriorityQueue<int> maxQueue;
    maxQueue.push(4);
    maxQueue.push(2);
    maxQueue.push(3);
    cout<<"利用默认比较函数建最大堆"<<endl;
    maxQueue.show();

    cout<<"利用自己定义的比较仿函数，建最小堆"<<endl;
    MyPriorityQueue<int,MyCompare<int>>minQueue;
    minQueue.push(3);
    minQueue.push(1);
    minQueue.push(2);
    minQueue.show();
}
int main()
{
    test01();
    return 0;
}