二叉堆是非常有特点的数据结构，可以采用简单的数组就能实现，当然链表的实现也是没有问题的，毕竟是一个二叉树问题，当然可以采用链表实现。采用数组实现时，可以找到两个特别明显的规律：
 
左儿子：L_Son = Parent * 2;
右儿子：R_Son = Parent * 2 + 1;
 
二叉堆是一颗完全填满的树，可能例外的是在底层，底层上的元素是从左到右填入，当然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用简单的基于小值的形式。主要完成的操作：1、最小值的删除操作，该操作会删除根节点，然后提升儿子节点来代替根节点，具体的实现过程中通过提升左右儿子中较小的作为父结点，依此提升直到到达最底层，这种实现方式叫做下虑法。2、数据的插入操作，插入操作可能会破坏二叉堆的结构，一般在最底层创建一个空穴，然后比较插入值与空穴父结点的值，如果大于父结点的值，那么直接插入到空穴中，如果小于父结点，则将父结点的值插入到刚创建的空穴中，在父结点所在位置上形成新的父结点，这时候再和父结点的父结点比较，具体操作如上所述，直到找到具体的插入地址。当结点个数为偶数时，在删除操作中需要注意节点是否有右儿子的情况。具体的可以参考代码中的说明。
 
具体的实现如下：
结构体：

    #ifndef __BINARYHEAP_H_H_
    #define __BINARYHEAP_H_H_

    #include
    #include

    #define bool int
    #define true 1
    #define false 0

    /*打算采用数组的方式实现完全二叉堆*/
    typedef struct _binaryheap
    {
            /*因为需要动态扩展，
            *采用静态数组不方便*/
            int * parray;
            /*目前存在的结点*/
            int currentSize;
            /*树的实际容量*/
            int capacity;
    }BinaryHeap_t, *BinaryHeap_handle_t;

    #ifdef __cplusplus
    extern "C"
    {
    #endif

    bool init_BinaryHeap(BinaryHeap_handle_t heap, int capacity);
    bool alloc_BinaryHeap(BinaryHeap_handle_t *heap, int capacity);
    void delete_BinaryHeap(BinaryHeap_handle_t heap);
    void free_BinaryHeap(BinaryHeap_handle_t *heap);

    bool insert(BinaryHeap_handle_t heap,int value);
    int deleteMin(BinaryHeap_handle_t heap);
    bool isEmpty(BinaryHeap_handle_t heap);

    #ifdef __cplusplus
    }
    #endif

    #endif

实现的接口函数如下：

    #include "binaryheap.h"

    bool isEmpty(BinaryHeap_handle_t heap)
    {
            assert(heap != NULL);
            return heap->currentSize == 0;
    }

    bool init_BinaryHeap(BinaryHeap_handle_t heap, int capacity)
    {
            int *parray = NULL;

            if(heap == NULL)
                    return false;
        
            parray = (int *)calloc(capacity+1,sizeof(int));
            if(parray == NULL)
                    return false;
        
            heap->parray = parray;
            heap->capacity = capacity;
            heap->currentSize = 0;

            return true;
    }

    void delete_BinaryHeap(BinaryHeap_handle_t heap)
    {
            assert(heap != NULL && heap->parray != NULL);

            heap->capacity = 0;
            heap->currentSize = 0;

            free(heap->parray);
            heap->parray = NULL;
    }

    void free_BinaryHeap(BinaryHeap_handle_t *heap)
    {
            assert(*heap != NULL);

            (*heap)->capacity = 0;
            (*heap)->currentSize = 0;

            free((*heap)->parray);
            (*heap)->parray = NULL;

            free(*heap);
            *heap = NULL;
    }

    bool alloc_BinaryHeap(BinaryHeap_handle_t *heap, int capacity)
    {
            int *parray = NULL;

            if(*heap != NULL)
                    return false;

            *heap = (int *)calloc(1, sizeof(BinaryHeap_t));
            if(*heap == NULL)
                    return false;

            /*其中的1，主要是为了使得数组从下标1开始计算*/
            parray =(int *)calloc(capacity + 1, sizeof(int));
            if(parray == NULL)
                    return false;

            (*heap)->parray = parray;
            (*heap)->capacity = capacity;
            (*heap)->currentSize = 0;

            return true;
    }

    /**************************************************
     * 采用上虑法实现数据的插入操作
     * 上虑法的实现方式比较简单，首先创建一个空节点
     * 然后将需要插入的值与当前空穴的父结点进行比较
     * 如果大于父结点，直接插入空穴中
     * 如果小于父结点的值，则将父结点的值下拉到空穴中
     * 之前父结点的位置就是空穴，接着与上层比较
     * 直到找到父结点大于当前插入值的情况
     **************************************************/
    bool insert(BinaryHeap_handle_t heap, int value)
    {
            int index = 0;

            if(heap == NULL || heap->parray == NULL)
                    return false;

            /*得到一个新的空穴下标*/
            index = ++heap->currentSize;
            /*条件是不是第一个下标和插入值比对应父结点小*/
            while(index > 1 && value < heap->parray[index/2])
            {
                    /*将父结点保存到当前结点处*/
                    heap->parray[index] = heap->parray[index/2];
                    /*得到父结点的空穴位置*/
                    index /= 2;
            }
            /*将插入的值保存到剩余的空穴中*/
            heap->parray[index] = value;

            return true;
    }

    /***********************************************************
     * 下虑法实现数据的重排序操作
     * 实现的方式，将子结点的两个儿子进行比较，将小的提升
     * 需要注意的是如何让判断节点是否一定存在右儿子
     * 实现的方式主要是利用了二叉堆的特性:
     * 2*pare = L_child
     * 2*pare + 1 = R_child;[page]
     ***********************************************************/
    static void presort_BinaryHeap(BinaryHeap_handle_t heap,int hole)
    {
            /*这是二叉堆的特性*/
            int child = hole * 2;
            /*保存当前数据操作*/
            int tmp = 0;

            assert(heap != NULL && heap->parray != NULL);

            tmp = heap->parray[hole];
            /*hold * 2 <= heap->currentSize 判断了当前结点是否为最低层*/
            for(; hole * 2 <= heap->currentSize; hole = child)
            {
                    child = hole * 2;

                    /*******************************
                    *这句代码解决是否存在右结点的问题
                    *并确定了那个子结点提升的问题
                    *******************************/
                    if((child != heap->currentSize)
                            && (heap->parray[child + 1] < heap->parray[child]))
                            child ++;

                    if(heap->parray[child] < tmp)
                    {
                            /*将子结点提升为父结点*/
                           heap->parray[hole] = heap->parray[child];
                    }
            }
            /*到达了最低的层，也就是树叶*/
            heap->parray[hole] = tmp;
    }

    /*实现数据的下虑法实现数据的删除操作*/
    int deleteMin(BinaryHeap_handle_t heap)
    {
            int ret = 0;
            int index = 0;

            assert(!isEmpty(heap));
            /*需要返回的值*/
            ret = heap->parray[1];

            /*将最后需要释放内存空间的值保存到第一个内存空间中*/
            heap->parray[1] = heap->parray[heap->currentSize --];
            /*从表头开始将新的二叉树进行重新排序*/
            presort_BinaryHeap(heap, 1);

            return ret;
    }

测试代码：

    #include "binaryheap.h"
    #include
    #include

    void print_binaryheap(BinaryHeap_handle_t heap)
    {
            int i = 0;

            assert(heap != NULL && heap->parray != NULL);

            for(i = 1; i <= heap->currentSize; ++ i)
            {
                    if(i %6)
                            printf("%d ",heap->parray[i]);
                    else
                            printf(" %d ",heap->parray[i]);
            }
            printf(" ");
    }

    int main()
    {
            int i = 0;
            int value = 0;

            srand((int)time(0));
            printf("********Test Binaryheap************** ");

            BinaryHeap_t bheap;
            BinaryHeap_handle_t *pheap = NULL;

            printf("init and alloc test: ");
            if(init_BinaryHeap(&bheap,10))
           {
                    printf("init_BinaryHeap() successed! ");
            }
            if (alloc_BinaryHeap(&pheap,15));
            {
                    printf("alloc_BInaryHeap() successed! ");
            }

            printf("***insert test***** ");
            for(; i < 10; ++ i)
            {
                    if(!insert(&bheap,5 * i - rand()%20))
                    {
                            printf("i = %d:insert failed !! ",i);
                    }
            }
            for(i = 0; i < 15; ++ i)
            {
                    if(!insert(pheap,i * 8 - rand()%20))
                    {
                            printf("i = %d:insert failed!! ",i);
                    }
            }

            print_binaryheap(&bheap);
            print_binaryheap(pheap);

            printf("****deleteMin test**** ");
            for(i = 0; i < 5; ++ i)
            {
                    value = deleteMin(&bheap);
                    printf("bheap deleted:%d ",value);
                    value = deleteMin(pheap);
                    printf("pheap deleted:%d ",value);
            }
            print_binaryheap(&bheap);
            print_binaryheap(pheap);

            printf("deleteMin test successed ");

            printf("****delete and free test:******* ");
            delete_BinaryHeap(&bheap);

            printf("Is the bheap empty ? %s ",
                            isEmpty(&bheap)?"Yes":"No");

            free_BinaryHeap(&pheap);

            printf("*********Test successed!*********** ");
            pheap = NULL;
            return 0;
    }

测试结果：

    [gong@Gong-Computer c_binaryheap]$ ./testbinaryheap
    ********Test Binaryheap**************
    init and alloc test:
    init_BinaryHeap()
    alloc_BInaryHeap()
    ***insert test*****
    -11    -9    -9    14    15    
    10    21    23    40    26    
    -16    2    14    20    13    
    21    33    49    61    67    76    
    86    83    95    109    
    ****deleteMin test****
    bheap deleted:-11
    pheap deleted:-16
    bheap deleted:-9
    pheap deleted:2
    bheap deleted:-9
    pheap deleted:13
    bheap deleted:10
    pheap deleted:14
    bheap deleted:14
    pheap deleted:20
    15    23    21    40    26    
    21    49    21    61    67    
    76    33    95    83    109    
    deleteMin test successed
    ****delete and free test:*******
    Is the bheap empty ? Yes
    *********Test

从上面的测试结果可知，基本上实现了二叉堆的基本插入、删除操作。代码的关键点在于删除中的下虑和插入过程中的上虑操作。以及如何判断代码是否存在右儿子，如何充分运用二叉堆的特性。