#ifndef HEAPSORT_H_
#define HEAPSORT_H_
#include <iostream>
template <class Type>
class HeapSort
{
private:
    Type* m_inputArr;    //原始输入队列,同时存储排好序的数组
    int m_length;        //堆长度
    bool m_detect;         //侦测是用到哪一个构造函数
    void getInput();     //获得输入
    void maxHeap(Type const*, const int, const int);      //保持最大堆性质
    void setupHeap(Type const*, const int);   //产生最大堆
    void sort(Type const*);      //总排序方法
public:
    HeapSort();
    HeapSort(Type*, int);
    ~HeapSort();
    int getLength(){
        return m_length; }
    void show();
};
template <class Type>
void HeapSort::getInput()
{
    using namespace std;
    cout <<"Please enter the length you wanna sort: ";
    while(!(cin >>m_length) || m_length<0 || cin.get()!='\n')
    {
        cerr <<"Error, enter a positive number:  ";
        cin.clear();
        while(cin.get()!='\n')
            continue;
    }
    m_inputArr = new Type[m_length+1];
    for(int i=0; i<<"\tenter="" #"<<<"="" number:="" ";="" while(!(cin="">>m_inputArr[i]) || m_length<0 || cin.get()!='\n')
        {
            cerr <<"Error, enter a positive number:  ";
            cin.clear();
            while(cin.get()!='\n')
                continue;
        }
    }
    m_inputArr[m_length] = '\0';
}
template <class Type>
void HeapSort::maxHeap(Type const* arr, const int node, const int size)
{
    int left = 2 * node + 1;
    int right = left + 1;
    int largest = node;
    if((leftm_inputArr[largest]))
        largest = right;
    if(largest != node)
    {
        m_inputArr[node] += m_inputArr[largest];
        m_inputArr[largest] = m_inputArr[node] - m_inputArr[largest];
        m_inputArr[node] -= m_inputArr[largest];
        maxHeap(arr, largest, size);
    }
}
template <class Type>
void HeapSort::setupHeap(Type const* arr, const int size)
{
    for(int i=(getLength()-1)/2; i>=0; i--)
        maxHeap(arr, i, size);
}
template <class Type>
void HeapSort::sort(Type const* arr)
{
    this->setupHeap(m_inputArr, getLength());
    int size = getLength();
    while(size>=2)
    {
        m_inputArr[size-1] += m_inputArr[0];
        m_inputArr[0] = m_inputArr[size-1] - m_inputArr[0];
        m_inputArr[size-1] -= m_inputArr[0];
        size--;
        this->maxHeap(arr, 0, size);
    }
}
template <class Type>
void HeapSort::show()
{
    using namespace std;
    cout <<"The ordered arrar is :\n\t";
    for(int i=0;i<<<"="" ";="" }="" <
HeapSort::HeapSort()
{
    this->getInput();
    this->sort(m_inputArr);
    this->m_detect = true;
}
template <class Type>
HeapSort::HeapSort(Type * arr, int length)
{
    m_inputArr = arr;
    m_length = length;
    this->sort(m_inputArr);
    this->m_detect = false;
}
template <class Type>
HeapSort::~HeapSort()
{
    if(m_detect)
        delete [] m_inputArr;
}
#endif