typedef int Heaptype;
 
typedef struct Heap
{
    Heaptype* head;   
    int size;         //記錄堆總?cè)萘?
    int capacity;     //記錄當(dāng)前數(shù)據(jù)總個數(shù)
}Heap;
 
//堆的初始化
void Heap_Init(Heap* pphead)
{
    assert(pphead);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

//向上調(diào)整
void adjust_up(Heap* pphead)
{
    int child = pphead->capacity;
    int parent = (child - 1) / 2;
    for (; pphead->head[parent] < pphead->head[child];)//判斷是否符合大頂堆
    {
        swap(&(pphead->head[parent]),&(pphead->head[child]));//進(jìn)行交換
        child = parent;
        parent = (child - 1) / 2;
    }
}
 
//插入數(shù)據(jù)
void Heap_push(Heap* pphead, Heaptype data)
{
    assert(pphead);
    //判斷是否滿容量并擴(kuò)容
    Heap_realloc(pphead);
    pphead->head[pphead->capacity] = data;
    //向上調(diào)整
    adjust_up(pphead);
    pphead->capacity++;
}

//刪除數(shù)據(jù)
void Heap_pop(Heap* pphead)
{
    assert(pphead);
    assert(pphead->capacity > 0);      //防止堆為空
    //將頂部數(shù)據(jù)與尾部數(shù)據(jù)交換
    swap(&(pphead->head[0]),&( pphead->head[pphead->capacity-1]));
    pphead->capacity--;
    //向下調(diào)整
    adjust_down(pphead,0);
}
 
//向下調(diào)整
void Adjust_down(int* a, int size, int parent)
{
    assert(a);
    for (int child = parent * 2 + 1; child <= size; child = parent * 2 + 1)
    {
        //默認(rèn)用左孩紙與母節(jié)點(diǎn)比較，如果右孩紙比左孩紙大且不越界則交換
        if (a[child] > a[child + 1] && child + 1 <= size)
            child = child + 1;
        //比較孩紙和母節(jié)點(diǎn)
        if (a[child] < a[parent])
        {
            int temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
        }
        //向下繼續(xù)比較
        parent = child;
    }
}

//判斷是否擴(kuò)容
void Heap_realloc(Heap* pphead)
{
    assert(pphead);
    if (pphead->size == pphead->capacity)
    {
        Heaptype Newsize = (pphead->size == 0) ? 4 : (pphead->size * 2);
        Heaptype* Newhead = (Heaptype*)realloc(pphead->head,sizeof(Heaptype) * Newsize);
        if (Newhead == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        pphead->head = Newhead;
        pphead->size = Newsize;
    }
}
 
//判斷堆是否為空
bool Heap_Empty(Heap* pphead)
{
    if (pphead->capacity)
        return false;
    return true;
}
//取對頂數(shù)據(jù)
Heaptype Heap_top(Heap* pphead)
{
    return pphead->head[0];
}
//銷毀堆
void Heap_Destory(Heap* pphead)
{
    assert(pphead);
    free(pphead->head);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}