C 算法精解-堆的兑现及分析

C 算法精解----堆的实现及分析
堆的描述

  堆是一种二叉树结构，通常是子节点的数值比父节点的值小，所以根节点是树种最大的节点。同样也可以说子节点的数值比父节点的数字大，所以根节点是树中最小的结点。子节点值比父节点值小的堆叫最大堆，反之，最小堆。下面来看下堆的性质：

父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

 堆的存储

   一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。下面是一个最大堆的图，及堆的遍历顺序（层次遍历，前面提到过）

  堆的实现与分析    头文件：

/*heap.h*/#ifndef HEAP_H#define HEAP_H/*定义一个堆得结构体*/typedef struct Heap_ {    /*堆中元素的个数*/    int size;    /* 比较节点和插入数值大小的函数指针*/    int (*compare)(const void *key1,const coid *key2);    /*当*tree是动态申请空间时，用来释放空间的函数指针*/    void (*destroy)(void *data);    /*tree 是堆中存储数据节点指针的数组*/    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.c*/#include <stdlib.h>#include <string.h>#include "heap.h"/*当前节点父节点的下标*/#define heap_parent(npos)  ((int)(((npos)-1)/2))/*当前节点左子树下标*/#define heap_left(npos) (((npos*2) + 1)/*当前节点右子树的下标*/#define heap_right(npos) (((npos)*2+2)/*初始化*/void heap_init(Heap * heap, int(* compare)(const void * key1, const void * key2), void(* destroy)(void * data)){    heap->size = 0;    heap ->compare = compare;    heap ->destroy = destroy;    heap ->tree = NULL;    return ;}/*销毁*/void heap_destroy(Heap * heap){    int i;    /*如果数据存放申请空间则删除*/    if (heap -> destroy != NULL){        for (i = 0, i < heap_size(heap), i++){              heap ->destroy(tree[i]);        }    }    /*释放数组空间*/    free (heap->tree);    memst(heap,0,sizeof(heap));    return;}

数据插入堆

先看下面个例子，就很明白函数的实现过程

/*将数据插入到最大值堆中  * 成功0;失败-1  **/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 : 保存插入数据节点的下标      * ppos: 保存插入数据父节点的下标      */    ipos = heap_size(heap);    ppos = heap_parent(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;}

删除根节点

/*释放堆顶部的节点*/int heap_extract(Heap * heap, void * * data){    void *save,*temp;    int ipos,lpos,rpos,mpos;    /*当堆为空时直接返回-1*/    if (heap_size(heap) == 0)        return -1;    /*获得根节点的数值*/    *data = heap->tree[0];    /*调整堆得存储空间大小save 指向tree的最后一个数据*/    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;        while (1){                lpos = heap_left(ipos);        rpos = heap_right(ipos);        if (lpos < heap_size(heap) && heap ->compare(heap->tree[lpos],heap->tree[ipos]) > 0){            mpos = lpos;        } else {            mpos = ipos;        }        if (lpos < heap_size(heap) && heap ->compare(heap->tree[rpos],heap->tree[ipos]) > 0){            mpos = rpos;        }         if (mpos == ipos){            break;        } else {            temp = heap->tree[mpos];            heap->tree[mpos] = heap->tree[ipos];            heap -> tree[ipos] = temp;            ipos = mpos;        }    }    return 0;}