#include <cstdlib>
#include "base.h"
typedef struct HeapStruct* MaxHeap;

struct HeapStruct{
    ElementType* Elements;
    int Size;
    int Capacity;
};

void Display(MaxHeap H)
{
    for(int i=1;i<=H->Size;++i)
    {
        cout<<H->Elements[i]<<" ";
    }
    cout<<endl;
}

MaxHeap Creat(int Capacity)
{//创建最大堆
    auto H=(MaxHeap)malloc(sizeof(struct HeapStruct));
    H->Size=0;
    H->Capacity=Capacity;
    H->Elements=(ElementType *)malloc((Capacity+1)*sizeof(int));
    H->Elements[0]=9999;
    return H;

}

void Insert(MaxHeap H,ElementType item)
{//插入
    if(H->Size>=H->Capacity)
    {
        cout<<"Heap is full!";
        return;
    }
    int index=++H->Size;
    for (; H->Elements[index/2] <item ; index/=2)
    {
        H->Elements[index]=H->Elements[index/2];
    }
    H->Elements[index]=item;
}

ElementType DeleteMax(MaxHeap H)
{//删除最大值
    if(H->Size<1)
    {
        cout<<"Heap is empty";
        return -9999;
    }
    ElementType MaxItem=H->Elements[1];
    ElementType tempItem=H->Elements[H->Size--];
    ElementType index,child;
    for(index=1;index*2<=H->Size;index=child)
    {
        child=index*2;
        if(child+1<=H->Size && H->Elements[child]<H->Elements[child+1])
        {
            child++;
        }
        if(tempItem>=H->Elements[child]) break;
        H->Elements[index]=H->Elements[child];
    }
    H->Elements[index]=tempItem;
    return MaxItem;

}

void AjustSubHeap(MaxHeap H,int root,int MaxLen)
{//调整某个 左右子树均是最大堆的子树 为最大堆 MaxLen用于控制堆的大小 便于实现堆排序
    ElementType tempItem=H->Elements[root];
    int index,child;
    for (index = root; index*2 <=MaxLen ; index=child)
    {
        child=index*2;
        if(child+1<=MaxLen && H->Elements[child]<H->Elements[child+1])
        {
            child++;
        }
        if(tempItem>=H->Elements[child]) break;
        H->Elements[index]=H->Elements[child];
    }
    H->Elements[index]=tempItem;
}

void InitHeap(MaxHeap H,const ElementType A[],int len)
{//给定N个元素初始化堆
    if(len>H->Capacity)
    {
        cout<<"The len of init array is out of the capacity of the heap!"<<endl;
    }
    for (int i = 0; i < len; ++i)
    {//初始化一颗完全二叉树
        H->Elements[i+1]=A[i];
        ++H->Size;
    }
//    Display(H);

    int StartIndex=H->Size/2;
    //自底向上调整成最大堆
    while (StartIndex>=1){
        AjustSubHeap(H,StartIndex,H->Size);
        StartIndex--;
    }
}

void HeapSort(ElementType A[],int len)
{//最大堆排序
    MaxHeap H= Creat(len);
    InitHeap(H,A,len);
    for (int i = len; i > 1; i--) {
        int temp=H->Elements[i];
        H->Elements[i]=H->Elements[1];
        H->Elements[1]=temp;
        AjustSubHeap(H,1,i-1);
    }
    Display(H);
}