//
//  main.cpp
//  Heap
//
//  Created by xin wang on 5/5/15.
//  Copyright (c) 2015 xin wang. All rights reserved.
//

#include <iostream>
class OutOfBound{
public:
     OutOfBound(){
        std::cout<<"越界"<<std::endl;
    }
};

class NoMen{
public:
    NoMen(){
        std::cout<<"No Men"<<std::endl;
    }
};

template <class T>
class MaxHeap{
public:
    MaxHeap(int MaxHeapSize=10);
    ~MaxHeap(){
        delete []heap;
    }
    int Size()const{
        return CurrentSize;
    }
    T Max(){
        if (CurrentSize==0) {
            throw OutOfBound();
        }
        return heap[1];

    }
    MaxHeap<T>& Insert(const T& x);
    MaxHeap<T>& DeleteMax(T& x);
    void Initialize(T a[],int size,int ArraySize);
    void Deactivate(){
        heap=0;
    }
private:
    int CurrentSize;
    int MaxSize;
    T *heap;
};

template <class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize){
    MaxSize = MaxHeapSize;
    heap = new T[MaxSize+1];
    CurrentSize=0;
}

//最大堆的插入
template <class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x){
    //把x插入到最大堆中
    if (CurrentSize==MaxSize) {
        throw NoMen();//没有足够的空间
    }
    int i= ++CurrentSize;
    while (i != 1&& x>heap[i/2]) {
        heap[i] = heap[i/2];//将元素下移
        i/=2;//移向父节点
    }
    heap[i]=x;
    return *this;
}

//最大堆的删除
template <class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x){
    //将最大元素放入x，并从堆中删除最大元素
    if (CurrentSize==0) {//越界
        throw OutOfBound();
    }
    
    x=heap[1];//将最大的元素放入x
    T y = heap[CurrentSize--];
    int i=1,ci=2;
    while (ci<=CurrentSize) {
        if (ci<CurrentSize && heap[ci]<heap[ci+1]) {
            ci++;//找到较大的孩子的位置
        }
        if (y>heap[ci]) {//能把y放入heap[i]
            break;
            
        }
        heap[i]=heap[ci];//将孩子上移
        i=ci;//下移一层
        ci*=2;
    }
    heap[i]=y;
    return *this;
    
    
}

template <class T>
void MaxHeap<T>::Initialize(T a[], int size, int ArraySize){
    delete []heap;
    heap=a;
    CurrentSize = size;
    MaxSize = ArraySize;
    
    for (int i= CurrentSize/2; i>=1; i--) {
        T y = heap[i];//子树的根
        
        int c = 2*i;
        while (c<=CurrentSize) {
            if (c <CurrentSize && heap[c]<heap[c+1]){
                c++;
            }
            if (y>=heap[c]) {
                break;
            }
            heap[c/2]=heap[c];//将孩子上移
            c*=2;//下移一层
        }
        heap[c/2]=y;

    }

}

template <class T>
void HeapSort(T a[],int n){
    //对a［1:n］进行排序
    MaxHeap<T> H(1);
    H.Initialize(a,n,n);
//    for (int ii=1; ii<=n; ii++) {
//        std::cout<<a[ii]<<" ";
//    }
    
    T x;
    std::cout<<"output:"<<std::endl;
    for (int i=n-1; i>=1; i--) {
        H.DeleteMax(x);
        std::cout<<x<<" ";
        a[i+1] =x;
    }
    H.Deactivate();//析构
}

int main(int argc, const char * argv[]) {
    // insert code here...,
    int array[20];
    std::cout<<"please enter an array,0 is end"<<std::endl;
    int i=0;
    int b=1;
    //初始化数组，输入0结束
    while(std::cin>>i){
        if (i==0) {
            break;
        }
        array[b]=i;
        b++;
        
    }
    
    HeapSort(array, b);
    return 0;
}