数据结构堆接口定义与实现分析（详细注释与图解）

/*heap.h*  堆的头文件/
#ifndef HEAP_H
#define HEAP_H

/*定义堆的数据结构体*/
typedef struct Heap_
{
    int size;
    
    int (*compare)(const void *key1,const void *key2);
    void (*destroy)(void *data);
    
    void **tree;
}Heap;

/*公共接口部分*/
void heap_init(Heap *heap,int (*compare)(const void *key1,const void key2),void (*destroy)(void *data));
void heap_destroy(Heap *heap);
int heap_insert(Heap *heap,const void *data);
int heap_extract(Heap *heap,void **data);

#define heap_size(heap)((heap)->size)

#endif // HEAP_H

/*heap.c*/
#include 
#include <string.h>

#include "heap.h"
/*定义heap执行中需要使用的私有宏*/
#define heap_parent(npos) ((int)(((npos)-1)/2))  /*npos的父结点*/
#define heap_left(npos) (((npos)*2)+1)           /*npos的左兄弟结点*/
#define heap_right(npos) (((npos)*2)+2)          /*npos的右兄弟结点*/

/*heap_init 堆的初始化*/
void heap_init(Heap *heap,int (*compare)(void *key1,void *key2),void (*destroy)(void *data))
{
    /*只需要将size设为0，destroy成员指向destroy，将tree指针设置为NULL*/
    heap->size = 0;
    heap->compare = compare;
    heap->destroy = destroy;
    heap->tree = NULL;

    return ;
}
/*heap_destroy  销毁堆*/
void heap_destroy(Heap *heap)
{
    int i;
    /*移除堆中所有的结点*/
    if(heap->destroy != NULL)
    {
        for(i=0; i)
        {
            /*调用用户自定义函数释放动态分配的数据*/
            heap->destroy(heap->tree[i]);
        }
    }
    /*释放为堆分配的空间*/
    free(heap->tree);

    memset(heap,0,sizeof(Heap));
    return;
}

/*heap_insert  向堆中插入结点*/
int heap_insert(Heap *heap,const void *data)
{
    void *temp;
    int  ipos;
         ppos;

    /*为结点分配空间*/
    if((temp = (void **)realloc(heap->tree,(heap->size(heap)+1)*sizeof(void *))) == NULL)
    {
        return -1;
    }
    else
    {
        heap->tree = temp;
    }
    /*将结点插入到堆的最末端*/
    heap->tree[heap_size(heap)] = (void *)data;
    /*将新结点向上推动，恢复堆的排序特点*/
    ipos = heap_size(heap);    /*堆结点数的数值*/
    ppos = heap_parent(ipos);  /*ipos位置结点的父结点*/

    /*如果堆不为空，并且末位结点大于其父结点，则将两个结点进行交换*/
    while(ipos>0 && heap->compare(heap->tree[ppos],heap->tree[ipos])<0)
    {
        /*交换末端结点与其父结点的位置*/
        temp = heap->tree[ppos];
        heap->tree[ppos] = heap->tree[ipos];
        heap->tree[ipos] = temp;

        /*将定位结点向上移动一层，以继续执行堆排序*/
        ipos = ppos;
        ppos = heap_parent(ipos);
    }

    /*堆插入与排序完成，调整堆的结点数量值*/
    heap->size++;

    return 0;
}

/*heap_extract 释放堆顶部的结点*/
int heap_extract(Heap *heap,void **data)
{
    void *save,
         *temp;
    int  ipos,lpos,rpos,mpos;

    /*不允许从空的堆中释放结点*/
    if(heap->size(heap) == 0)
        return -1;

    /*释放堆顶部的结点*/
    /*首先将data指向将要释放结点的数据*/
    *data = heap->tree[0]

    /*将save指向未位结点*/
    save = heap->tree[heap_size(heap)-1];

    if(heap_size(heap)-1 > 0)
    {   /*为堆分配一个稍小一点的空间*/
        if((temp = (void **)realloc(heap->tree,(heap_size(heap)-1)*sizeof(void *)))==NULL)
        {
            return -1;
        }
        else
        {
            heap->tree = temp;
        }
        /*调整堆的大小*/
        heap->size--;
    }
    else
    {   /*只有一个结点，释放并重新管理堆，并返回*/
        free(heap->tree);
        heap->tree = NULL;
        heap->size = 0;
        return 0;
    }
    /*将末位结点拷贝到根结点中*/
    heap->tree[0] = save;

    /*重新调整树的结构*/
    ipos = 0;                /*顶元素*/
    lpos = heap_left(ipos);  /*左子结点*/
    rpos = heap_right(ipos); /*右子结点*/

    /*父结点与两个子结点比较、交换，直到不再需要交换为止，或者结点到达一个叶子位置*/
    while(1)
    {
        /*选择子结点与当前结点进行交换*/
        lpos = heap_left(ipos);
        rpos = heap_right(ipos);
        /*父结点与左子结点位置不正确,左子结点大于其父结点*/
        if(lpos compare(heap->tree[lpos],heap->tree[ipos])>0)
        {
            mpos = lpos;  /*将左子结点的位置赋给mpos(最大位置)*/
        }
        else
        {
            mpos = ipos;
        }

        if(rpos compare(heap->tree[rpos],heap->tree[mpos])>0)
        {
            mpos = rpos;
        }

        /*当mpos和ipos相等时，堆特性已经被修复,结束循环*/
        if(mpos == ipos)
        {
            break;
        }
        else
        {
            /*交换当前结点与被选中的结点的内容*/
            temp = heap->tree[mpos];
            heap->tree[mpos] = heap->tree[ipos];
            heap->tree[ipos] = temp;

            /*下移一层，以继续执行堆排序*/
            ipos = mpos;
        }
    }
    return 0;
}