大根堆的实现

堆结构介绍：

• 大根堆：根结点的值比它的左右子树都要大，同时它的左右子树也遵循这项规则，也就是说一棵树的根结点中存储的是这棵树中的最大值，这种完全二叉树叫大根堆。

• 小根堆：根结点的值比它的左右子树都要小，同时它的左右子树也遵循这项规则，也就是说一棵树的根结点中存储的是这棵树中的最小值，这种完全二叉树叫小根堆。

• 堆结构是是一种特殊的完全二叉树，它与堆栈完全不同且没有任何关系，我们可以从堆中顺序获取堆顶的数据，也可以使用大根堆、小根堆的规则可以对顺序表进行排序。

#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define PARENT(index)       ((index+1)/2-1)
#define LEFT_CHILD(index)   ((index+1)*2-1) 
#define RIGHT_CHILD(index)  ((index+1)*2)

#define swap_mem(p1,p2,size) do{    \
    char temp[size];                \
    memcpy(temp,p1,size);           \
    memcpy(p1,p2,size);             \
    memcpy(p2,temp,size);           \
}while(0)

#define swap(a,b) swap_mem(&a,&b,sizeof(a))


typedef struct MaxHeap
{
    int* base;
    size_t cnt;
    size_t cal;
}MaxHeap;

// 把base中的数据调整为堆结构
void adjust_max_heap(MaxHeap* heap,int index)
{
    // 从index下标处，向上调整堆结构
    while(index > 0)
    {
        // 计算出双亲下标
        int parent = PARENT(index);
        // 计算出双亲结点的左子树
        int left = LEFT_CHILD(parent);
        // 如果左子树下标合法并且值大于双亲，则与双亲交换
        if(left < heap->cnt && heap->base[left] > heap->base[parent])
            swap(heap->base[left],heap->base[parent]);

        int right = RIGHT_CHILD(parent);
        // 如果右子树下标合法并且值大于双亲，则与双亲交换
        if(right < heap->cnt && heap->base[right] > heap->base[parent])
            swap(heap->base[right],heap->base[parent]);
    
        // 向上一层
        index = parent;
    }

}

// 创建一个空堆
MaxHeap* create_max_heap(size_t cal)
{
    MaxHeap* heap = malloc(sizeof(MaxHeap));
    heap->base = malloc(sizeof(int)*cal);
    heap->cal = cal;
    heap->cnt = 0;
    return heap;
}

// 初始化堆
MaxHeap* init_max_heap(int* arr,size_t len)
{
    MaxHeap* heap = malloc(sizeof(MaxHeap));
    heap->base = malloc(sizeof(int)*len);
    memcpy(heap->base,arr,sizeof(int)*len);
    heap->cal = len;
    heap->cnt = len;

    // 从叶子结点出发向上调整,最后一个叶子结点的双亲结点就是最后一个非叶子结点
    for(int i=len-1; i>len/2; i--)
        adjust_max_heap(heap,i);
    
    return heap;

}


// 销毁堆
void destroy_max_heap(MaxHeap* heap)
{
    free(heap->base);
    free(heap);
}

// 堆是否为空
bool empty_max_heap(MaxHeap* heap)
{
    return 0 == heap->cnt;
}

// 堆是否为满
bool full_max_heap(MaxHeap* heap)
{
    return heap->cal == heap->cnt;
}

// 入堆
bool push_max_heap(MaxHeap* heap,int val)
{
    if(full_max_heap(heap))
        return false;
    

    // 在末尾添加一个新结点
    heap->base[heap->cnt++] = val;
    // 从最后一个结点出发向上调整
    adjust_max_heap(heap,heap->cnt-1);

}

// 出堆
bool pop_max_heap(MaxHeap* heap)
{
    if(empty_max_heap(heap))
        return false;

    // 使用最后一个结点覆盖根结点,并且结点的数量减1
    heap->base[0] = heap->base[--heap->cnt];
    
    // 从根结点出发向下调整
    int parent = 0;
    while(parent < heap->cnt)
    {
        // 假定根结点是根、左右中的最大结点,并计算出它的左右子树的下标
        int max=parent, left=LEFT_CHILD(parent),right=RIGHT_CHILD(parent);
        
        // 如果左子树下标合法，且左子树的值大于最大结点，则把左子记作最大结点
        if(left < heap->cnt && heap->base[max] < heap->base[left])
            max = left;
        // 如果右子树下标合法，且右子树的值大于最大结点，则把右子记作最大结点
        if(right < heap->cnt && heap->base[max] < heap->base[right])
            max = right;
    
        // 如果最大结点就是根结点，则不需要再向下调整，
        if(max == parent)
            break;
    
        // 把最大结点与根结点交换，从从大结点处继续向下调整
        swap(heap->base[max],heap->base[parent]);
        parent = max;
    }
    return true;

}

// 堆顶
int top_max_heap(MaxHeap* heap)
{
    if(empty_max_heap(heap))
        return -1;
    return heap->base[0];
}

// 元素数量
size_t size_max_heap(MaxHeap* heap)
{
    return heap->cnt;
}   

int main(int argc,const char* argv[])
{
    MaxHeap* heap = create_max_heap(10);
    int arr[10];
    for(int i=0; i<10; i++)
    {
        arr[i] = rand() % 100;
        printf("%d ",arr[i]);
        push_max_heap(heap,arr[i]);
    }
    printf("\n");
    while(!empty_max_heap(heap))
    {
        printf("%d ",top_max_heap(heap));
        pop_max_heap(heap);
    }
    return 0;
}