二叉堆的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中如何使用，我任務主要是在操作系統(tǒng)中的任務優(yōu)先級調(diào)度問題，當然也可以用于實現(xiàn)堆排序問題，比如找出數(shù)組中的第K個最小值問題，采用二叉堆能夠快速的實現(xiàn)，今天我就采用C語言實現(xiàn)了一個簡單的二叉堆操作，完成這些數(shù)據(jù)結(jié)構(gòu)我并不知道能干什么，我就當自己在練習C語言的功底吧。逐步完成自己的代碼，希望自己在知識的理解力上有一定的提高。
二叉堆是非常有特點的數(shù)據(jù)結(jié)構(gòu)，可以采用簡單的數(shù)組就能實現(xiàn)，當然鏈表的實現(xiàn)也是沒有問題的，畢竟是一個二叉樹問題，當然可以采用鏈表實現(xiàn)。采用數(shù)組實現(xiàn)時，可以找到兩個特別明顯的規(guī)律：
左兒子：L_Son = Parent * 2;
右兒子：R_Son = Parent * 2 + 1;
二叉堆是一顆完全填滿的樹，可能例外的是在底層，底層上的元素是從左到右填入，當然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用簡單的基于小值的形式。主要完成的操作：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é)點比較，具體操作如上所述，直到找到具體的插入地址。當結(jié)點個數(shù)為偶數(shù)時，在刪除操作中需要注意節(jié)點是否有右兒子的情況。具體的可以參考代碼中的說明。
具體的實現(xiàn)如下：
結(jié)構(gòu)體：
#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_
#include <stdlib.h>
#include <assert.h>
#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ù)組從下標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é)點
* 然后將需要插入的值與當前空穴的父結(jié)點進行比較
* 如果大于父結(jié)點，直接插入空穴中
* 如果小于父結(jié)點的值，則將父結(jié)點的值下拉到空穴中
* 之前父結(jié)點的位置就是空穴，接著與上層比較
* 直到找到父結(jié)點大于當前插入值的情況
**************************************************/
bool insert（BinaryHeap_handle_t heap, int value）
{
int index = 0;
if（heap == NULL || heap->parray == NULL）
return false;
/*得到一個新的空穴下標*/
index = ++heap->currentSize;
/*條件是不是第一個下標和插入值比對應父結(jié)點小*/
while（index > 1 && value < heap->parray[index/2]）
{
/*將父結(jié)點保存到當前結(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;
***********************************************************/
static void presort_BinaryHeap（BinaryHeap_handle_t heap,int hole）
{
/*這是二叉堆的特性*/
int child = hole * 2;
/*保存當前數(shù)據(jù)操作*/
int tmp = 0;
assert（heap != NULL && heap->parray != NULL）；
tmp = heap->parray[hole];
/*hold * 2 <= heap->currentSize 判斷了當前結(jié)點是否為最低層*/
for（； hole * 2 <= heap->currentSize; hole = child）
{
child = hole * 2;
/*******************************
*這句代碼解決是否存在右結(jié)點的問題
*并確定了那個子結(jié)點提升的問題
*******************************/
if（（child != heap->currentSize）
&& （heap->parray[child + 1] < heap->parray[child]））
child ++;
if（heap->parray[child] < tmp）
{
/*將子結(jié)點提升為父結(jié)點*/
heap->parray[hole] = heap->parray[child];
}
}
/*到達了最低的層，也就是樹葉*/
heap->parray[hole] = tmp;
}
/*實現(xiàn)數(shù)據(jù)的下慮法實現(xiàn)數(shù)據(jù)的刪除操作*/
int deleteMin（BinaryHeap_handle_t heap）
{
int ret = 0;
int index = 0;
assert（！isEmpty（heap））；
/*需要返回的值*/
ret = heap->parray[1];
/*將最后需要釋放內(nèi)存空間的值保存到第一個內(nèi)存空間中*/
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）[nettpage]
{
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）；
printf（"*********Test successed!***********\n"）；
pheap = NULL;
return 0;
}
測試結(jié)果：
[gong@Gong-Computer c_binaryheap]$ ./testbinaryheap
********Test Binaryheap**************
init and alloc test:
init_BinaryHeap（）
alloc_BInaryHeap（）
***insert test*****
-11 -9 -9 14 15
10 21 23 40 26
-16 2 14 20 13
21 33 49 61 67 76
86 83 95 109
****deleteMin test****
bheap deleted:-11
pheap deleted:-16
bheap deleted:-9
pheap deleted:2
bheap deleted:-9
pheap deleted:13
bheap deleted:10
pheap deleted:14
bheap deleted:14
pheap deleted:20
15 23 21 40 26
21 49 21 61 67
76 33 95 83 109
deleteMin test successed
****delete and free test:*******
Is the bheap empty ? Yes
*********Test
從上面的測試結(jié)果可知，基本上實現(xiàn)了二叉堆的基本插入、刪除操作。代碼的關(guān)鍵點在于刪除中的下慮和插入過程中的上慮操作。以及如何判斷代碼是否存在右兒子，如何充分運用二叉堆的特性。 二叉堆的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中如何使用，我任務主要是在操作系統(tǒng)中的任務優(yōu)先級調(diào)度問題，當然也可以用于實現(xiàn)堆排序問題，比如找出數(shù)組中的第K個最小值問題，采用二叉堆能夠快速的實現(xiàn)，今天我就采用C語言實現(xiàn)了一個簡單的二叉堆操作，完成這些數(shù)據(jù)結(jié)構(gòu)我并不知道能干什么，我就當自己在練習C語言的功底吧。逐步完成自己的代碼，希望自己在知識的理解力上有一定的提高。
二叉堆是非常有特點的數(shù)據(jù)結(jié)構(gòu)，可以采用簡單的數(shù)組就能實現(xiàn)，當然鏈表的實現(xiàn)也是沒有問題的，畢竟是一個二叉樹問題，當然可以采用鏈表實現(xiàn)。采用數(shù)組實現(xiàn)時，可以找到兩個特別明顯的規(guī)律：
左兒子：L_Son = Parent * 2;
右兒子：R_Son = Parent * 2 + 1;
二叉堆是一顆完全填滿的樹，可能例外的是在底層，底層上的元素是從左到右填入，當然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用簡單的基于小值的形式。主要完成的操作：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é)點比較，具體操作如上所述，直到找到具體的插入地址。當結(jié)點個數(shù)為偶數(shù)時，在刪除操作中需要注意節(jié)點是否有右兒子的情況。具體的可以參考代碼中的說明。
具體的實現(xiàn)如下：
結(jié)構(gòu)體：
#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_
#include <stdlib.h>
#include <assert.h>
#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ù)組從下標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é)點
* 然后將需要插入的值與當前空穴的父結(jié)點進行比較
* 如果大于父結(jié)點，直接插入空穴中
* 如果小于父結(jié)點的值，則將父結(jié)點的值下拉到空穴中
* 之前父結(jié)點的位置就是空穴，接著與上層比較
* 直到找到父結(jié)點大于當前插入值的情況
**************************************************/
bool insert（BinaryHeap_handle_t heap, int value）
{
int index = 0;
if（heap == NULL || heap->parray == NULL）
return false;
/*得到一個新的空穴下標*/
index = ++heap->currentSize;
/*條件是不是第一個下標和插入值比對應父結(jié)點小*/
while（index > 1 && value < heap->parray[index/2]）
{
/*將父結(jié)點保存到當前結(jié)點處*/
heap->parray[index] = heap->parray[index/2];
/*得到父結(jié)點的空穴位置*/
index /= 2;
}
/*將插入的值保存到剩余的空穴中*/
heap->parray[index] = value;
return true;
}
/***********************************************************
* 下慮法實現(xiàn)數(shù)據(jù)的重排序操作
* 實現(xiàn)的方式，將子結(jié)點的兩個兒子進行比較tbw，將小的提升
* 需要注意的是如何讓判斷節(jié)點是否一定存在右兒子
* 實現(xiàn)的方式主要是利用了二叉堆的特性：
* 2*pare = L_child
* 2*pare + 1 = R_child;
***********************************************************/
static void presort_BinaryHeap（BinaryHeap_handle_t heap,int hole）
{
/*這是二叉堆的特性*/
int child = hole * 2;
/*保存當前數(shù)據(jù)操作*/
int tmp = 0;
assert（heap != NULL && heap->parray != NULL）；
tmp = heap->parray[hole];
/*hold * 2 <= heap->currentSize 判斷了當前結(jié)點是否為最低層*/
for（； hole * 2 <= heap->currentSize; hole = child）
{
child = hole * 2;
/*******************************
*這句代碼解決是否存在右結(jié)點的問題
*并確定了那個子結(jié)點提升的問題
*******************************/
if（（child != heap->currentSize）
&& （heap->parray[child + 1] < heap->parray[child]））
child ++;
if（heap->parray[child] < tmp）
{
/*將子結(jié)點提升為父結(jié)點*/
heap->parray[hole] = heap->parray[child];
}
}
/*到達了最低的層，也就是樹葉*/
heap->parray[hole] = tmp;
}
/*實現(xiàn)數(shù)據(jù)的下慮法實現(xiàn)數(shù)據(jù)的刪除操作*/
int deleteMin（BinaryHeap_handle_t heap）
{
int ret = 0;
int index = 0;
assert（！isEmpty（heap））；
/*需要返回的值*/
ret = heap->parray[1];
/*將最后需要釋放內(nèi)存空間的值保存到第一個內(nèi)存空間中*/
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）；
printf（"*********Test successed!***********\n"）；
pheap = NULL;
return 0;
}
測試結(jié)果：
[gong@Gong-Computer c_binaryheap]$ ./testbinaryheap
********Test Binaryheap**************
init and alloc test:
init_BinaryHeap（）
alloc_BInaryHeap（）
***insert test*****
-11 -9 -9 14 15
10 21 23 40 26
-16 2 14 20 13
21 33 49 61 67 76
86 83 95 109
****deleteMin test****
bheap deleted:-11
pheap deleted:-16
bheap deleted:-9
pheap deleted:2
bheap deleted:-9
pheap deleted:13
bheap deleted:10
pheap deleted:14
bheap deleted:14
pheap deleted:20
15 23 21 40 26
21 49 21 61 67
76 33 95 83 109
deleteMin test successed
****delete and free test:*******
Is the bheap empty ? Yes
*********Test
從上面的測試結(jié)果可知，基本上實現(xiàn)了二叉堆的基本插入、刪除操作。tbw代碼的關(guān)鍵點在于刪除中的下慮和插入過程中的上慮操作。以及如何判斷代碼是否存在右兒子，如何充分運用二叉堆的特性。