#include <stdio.h>
#include <stdlib.h>
#include <iostream>

#define LEN 11

using namespace std;

typedef struct Heap{
    int  len;
    int* base;
}Heap; 

void swap(int* a , int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void init(Heap* heap,int len)
{
    heap->len  = len;
    heap->base = (int*)malloc(len * sizeof(int));
    
    
    for(int i = 0;i < heap->len; i++)        //生成的全部数字置为0 
        heap->base[i]=0;

}

int insert(Heap* heap,int* array,int array_len)
{
    if(array_len>heap->len) return -1;        //越界异常 
    for(int i =0;i<array_len;i++)
    {
        heap->base[i]=array[i];
    }
    return 0;
}

void max_heapify(Heap* heap,int len)
{
    for(int l = len/2 -1;l > 0; l--)
    {
        if(heap->base[l*2] > heap->base[l] && heap->base[l*2+1] < heap->base[l*2])
        {
            swap(heap->base[l*2],heap->base[l]);
        }
        if(heap->base[l*2+1] > heap->base[l] && heap->base[l*2] < heap->base[l*2+1])
        {
            swap(heap->base[l*2+1],heap->base[l]);
        }
    }
}

void heap_sort(Heap* heap,int* array)
{
    int cnt = 0;
    int len = heap->len;
    do
    {
        array[cnt++]=heap->base[0];
        swap(heap->base[0],heap->base[len-1]);
        max_heapify(heap,--len);
    }while(len);
}

void traverse(Heap heap)
{
    for(int i = 0;i < heap.len; i++)
    {
        cout<<heap.base[i]<<endl;
    }
}
int main()
{
    Heap heap;
    int array[LEN]={15,12,10,16,4,3,1,8,11,3,6};
    
    init(&heap,LEN);
    if(!~insert(&heap,array,LEN)) cout<<"越界"<<endl;
    max_heapify(&heap,LEN);
    traverse(heap);
    putchar(10);
    heap_sort(&heap,array);
    for(int i =0;i<LEN;i++)
    {
        cout<<array[i]<<endl;
    }
    return 0;
}