二叉堆的C語言實現

二叉堆是非常有特點的數據結構，可以采用簡單的數組就能實現，當然鏈表的實現也是沒有問題的，畢竟是一個二叉樹問題，當然可以采用鏈表實現。采用數組實現時，可以找到兩個特別明顯的規律：

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

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

具體的實現如下：
結構體：

#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_

#include
#include

#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;