二叉堆的C语言实现

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;
***********************************************************/
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