二叉堆的C语言实现

二叉堆的实现数据结构中如何使用，我任务主要是在操作系统中的任务优先级调度问题，当然也可以用于实现堆排序问题，比如找出数组中的第K个最小值问题，采用二叉堆能够快速的实现，今天我就采用C语言实现了一个简单的二叉堆操作，完成这些数据结构我并不知道能干什么，我就当自己在练习C语言的功底吧。逐步完成自己的代码，希望自己在知识的理解力上有一定的提高。 二叉堆是非常有特点的数据结构，可以采用简单的数组就能实现，当然链表的实现也是没有问题的，毕竟是一个二叉树问题，当然可以采用链表实现。采用数组实现时，可以找到两个特别明显的规律： 左儿子：L_Son = Parent * 2; 右儿子：R_Son = Parent * 2 + 1; 二叉堆是一颗完全填满的树，可能例外的是在底层，底层上的元素是从左到右填入，当然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用简单的基于小值的形式。主要完成的操作：1、最小值的删除操作，该操作会删除根节点，然后提升儿子节点来代替根节点，具体的实现过程中通过提升左右儿子中较小的作为父结点，依此提升直到到达最底层，这种实现方式叫做下虑法。2、数据的插入操作，插入操作可能会破坏二叉堆的结构，一般在最底层创建一个空穴，然后比较插入值与空穴父结点的值，如果大于父结点的值，那么直接插入到空穴中，如果小于父结点，则将父结点的值插入到刚创建的空穴中，在父结点所在位置上形成新的父结点，这时候再和父结点的父结点比较，具体操作如上所述，直到找到具体的插入地址。当结点个数为偶数时，在删除操作中需要注意节点是否有右儿子的情况。具体的可以参考代码中的说明。 具体的实现如下： 结构体：

#ifndef __BINARYHEAP_H_H_ #define __BINARYHEAP_H_H_

#include <stdlib.h> #include <assert.h>

#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; ***********************************************************/ 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 <stdio.h> #include <time.h>

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\t",heap->parray[i]); else printf("\n%d\t",heap->parray[i]); } printf("\n"); }

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

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

BinaryHeap_t bheap; BinaryHeap_handle_t *pheap = NULL;

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

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

print_binaryheap(&bheap); print_binaryheap(pheap);

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

printf("deleteMin test successed\n");

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

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

free_BinaryHeap(&pheap);</