二叉堆的C語言實(shí)現(xiàn)

二叉堆是非常有特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，可以采用簡(jiǎn)單的數(shù)組就能實(shí)現(xiàn)，當(dāng)然鏈表的實(shí)現(xiàn)也是沒有問題的，畢竟是一個(gè)二叉樹問題，當(dāng)然可以采用鏈表實(shí)現(xiàn)。采用數(shù)組實(shí)現(xiàn)時(shí)，可以找到兩個(gè)特別明顯的規(guī)律：

左兒子：L_Son = Parent * 2;
右兒子：R_Son = Parent * 2 + 1;

二叉堆是一顆完全填滿的樹，可能例外的是在底層，底層上的元素是從左到右填入，當(dāng)然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用簡(jiǎn)單的基于小值的形式。主要完成的操作：1、最小值的刪除操作，該操作會(huì)刪除根節(jié)點(diǎn)，然后提升兒子節(jié)點(diǎn)來代替根節(jié)點(diǎn)，具體的實(shí)現(xiàn)過程中通過提升左右兒子中較小的作為父結(jié)點(diǎn)，依此提升直到到達(dá)最底層，這種實(shí)現(xiàn)方式叫做下慮法。2、數(shù)據(jù)的插入操作，插入操作可能會(huì)破壞二叉堆的結(jié)構(gòu)，一般在最底層創(chuàng)建一個(gè)空穴，然后比較插入值與空穴父結(jié)點(diǎn)的值，如果大于父結(jié)點(diǎn)的值，那么直接插入到空穴中，如果小于父結(jié)點(diǎn)，則將父結(jié)點(diǎn)的值插入到剛創(chuàng)建的空穴中，在父結(jié)點(diǎn)所在位置上形成新的父結(jié)點(diǎn)，這時(shí)候再和父結(jié)點(diǎn)的父結(jié)點(diǎn)比較，具體操作如上所述，直到找到具體的插入地址。當(dāng)結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，在刪除操作中需要注意節(jié)點(diǎn)是否有右兒子的情況。具體的可以參考代碼中的說明。

具體的實(shí)現(xiàn)如下：
結(jié)構(gòu)體：

#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_

#include
#include

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

/*打算采用數(shù)組的方式實(shí)現(xiàn)完全二叉堆*/
typedef struct _binaryheap
{
/*因?yàn)樾枰獎(jiǎng)討B(tài)擴(kuò)展，
*采用靜態(tài)數(shù)組不方便*/
int * parray;
/*目前存在的結(jié)點(diǎn)*/
int currentSize;
/*樹的實(shí)際容量*/
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

實(shí)現(xiàn)的接口函數(shù)如下：

#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，主要是為了使得數(shù)組從下標(biāo)1開始計(jì)算*/
parray =(int *)calloc(capacity + 1, sizeof(int));
if(parray == NULL)
return false;

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

return true;
}

/**************************************************
* 采用上慮法實(shí)現(xiàn)數(shù)據(jù)的插入操作
* 上慮法的實(shí)現(xiàn)方式比較簡(jiǎn)單，首先創(chuàng)建一個(gè)空節(jié)點(diǎn)
* 然后將需要插入的值與當(dāng)前空穴的父結(jié)點(diǎn)進(jìn)行比較
* 如果大于父結(jié)點(diǎn)，直接插入空穴中
* 如果小于父結(jié)點(diǎn)的值，則將父結(jié)點(diǎn)的值下拉到空穴中
* 之前父結(jié)點(diǎn)的位置就是空穴，接著與上層比較
* 直到找到父結(jié)點(diǎn)大于當(dāng)前插入值的情況
**************************************************/
bool insert(BinaryHeap_handle_t heap, int value)
{
int index = 0;

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

/*得到一個(gè)新的空穴下標(biāo)*/
index = ++heap->currentSize;
/*條件是不是第一個(gè)下標(biāo)和插入值比對(duì)應(yīng)父結(jié)點(diǎn)小*/
while(index > 1 && value < heap->parray[index/2])
{
/*將父結(jié)點(diǎn)保存到當(dāng)前結(jié)點(diǎn)處*/
heap->parray[index] = heap->parray[index/2];
/*得到父結(jié)點(diǎn)的空穴位置*/
index /= 2;
}
/*將插入的值保存到剩余的空穴中*/
heap->parray[index] = value;

return true;
}

/***********************************************************
* 下慮法實(shí)現(xiàn)數(shù)據(jù)的重排序操作
* 實(shí)現(xiàn)的方式，將子結(jié)點(diǎn)的兩個(gè)兒子進(jìn)行比較，將小的提升
* 需要注意的是如何讓判斷節(jié)點(diǎn)是否一定存在右兒子
* 實(shí)現(xiàn)的方式主要是利用了二叉堆的特性:
* 2*pare = L_child
* 2*pare + 1 = R_child;