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

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

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

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

具體的實現(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ù)組的方式實現(xiàn)完全二叉堆*/
typedef struct _binaryheap
{
/*因為需要動態(tài)擴展，
*采用靜態(tài)數(shù)組不方便*/
int * parray;
/*目前存在的結(jié)點*/
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

實現(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開始計算*/
parray =(int *)calloc(capacity + 1, sizeof(int));
if(parray == NULL)
return false;

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

return true;
}

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

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

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

return true;
}

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