二叉堆的C語(yǔ)言實(shí)現

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

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

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

具體的實(shí)現如下：
結構體：

#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_

#include
#include

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

/*打算采用數組的方式實(shí)現完全二叉堆*/
typedef struct _binaryheap
{
/*因為需要動(dòng)態(tài)擴展，
*采用靜態(tài)數組不方便*/
int * parray;
/*目前存在的結點(diǎn)*/
int currentSize;
/*樹(shù)的實(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í)現的接口函數如下：

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

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

return true;
}

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

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

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

return true;
}

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