二叉堆的实现数据结构中如何使用，我任务主要是在操作系统中的任务优先级调度问题，当然也可以用于实现堆排序问题，比如找出数组中的第K个最小值问题，采用二叉堆能够快速的实现，今天我就采用C语言实现了一个简单的二叉堆操作，完成这些数据结构我并不知道能干什么，我就当自己在练习C语言的功底吧。逐步完成自己的代码，希望自己在知识的理解力上有一定的提高。
二叉堆是非常有特点的数据结构，可以采用简单的数组就能实现，当然链表的实现也是没有问题的，毕竟是一个二叉树问题，当然可以采用链表实现。采用数组实现时，可以找到两个特别明显的规律：
左儿子：L_Son = Parent * 2;
右儿子：R_Son = Parent * 2 + 1;
二叉堆是一颗完全填满的树，可能例外的是在底层，底层上的元素是从左到右填入，当然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用简单的基于小值的形式。主要完成的操作：1、最小值的删除操作，该操作会删除根节点，然后提升儿子节点来代替根节点，具体的实现过程中通过提升左右儿子中较小的作为父结点，依此提升直到到达最底层，这种实现方式叫做下虑法。2、数据的插入操作，插入操作可能会破坏二叉堆的结构，一般在最底层创建一个空穴，然后比较插入值与空穴父结点的值，如果大于父结点的值，那么直接插入到空穴中，如果小于父结点，则将父结点的值插入到刚创建的空穴中，在父结点所在位置上形成新的父结点，这时候再和父结点的父结点比较，具体操作如上所述，直到找到具体的插入地址。当结点个数为偶数时，在删除操作中需要注意节点是否有右儿子的情况。具体的可以参考代码中的说明。
具体的实现如下：
结构体：
#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_
#include <stdlib.h>
#include <assert.h>
#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;
***********************************************************/
static void presort_BinaryHeap（BinaryHeap_handle_t heap,int hole）
{
/*这是二叉堆的特性*/
int child = hole * 2;
/*保存当前数据操作*/
int tmp = 0;
assert（heap != NULL && heap->parray != NULL）；
tmp = heap->parray[hole];
/*hold * 2 <= heap->currentSize 判断了当前结点是否为最低层*/
for（； hole * 2 <= heap->currentSize; hole = child）
{
child = hole * 2;
/*******************************
*这句代码解决是否存在右结点的问题
*并确定了那个子结点提升的问题
*******************************/
if（（child != heap->currentSize）
&& （heap->parray[child + 1] < heap->parray[child]））
child ++;
if（heap->parray[child] < tmp）
{
/*将子结点提升为父结点*/
heap->parray[hole] = heap->parray[child];
}
}
/*到达了最低的层，也就是树叶*/
heap->parray[hole] = tmp;
}
/*实现数据的下虑法实现数据的删除操作*/
int deleteMin（BinaryHeap_handle_t heap）
{
int ret = 0;
int index = 0;
assert（！isEmpty（heap））；
/*需要返回的值*/
ret = heap->parray[1];
/*将最后需要释放内存空间的值保存到第一个内存空间中*/
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;
}
测试结果：
[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
从上面的测试结果可知，基本上实现了二叉堆的基本插入、删除操作。代码的关键点在于删除中的下虑和插入过程中的上虑操作。以及如何判断代码是否存在右儿子，如何充分运用二叉堆的特性。 二叉堆的实现数据结构中如何使用，我任务主要是在操作系统中的任务优先级调度问题，当然也可以用于实现堆排序问题，比如找出数组中的第K个最小值问题，采用二叉堆能够快速的实现，今天我就采用C语言实现了一个简单的二叉堆操作，完成这些数据结构我并不知道能干什么，我就当自己在练习C语言的功底吧。逐步完成自己的代码，希望自己在知识的理解力上有一定的提高。
二叉堆是非常有特点的数据结构，可以采用简单的数组就能实现，当然链表的实现也是没有问题的，毕竟是一个二叉树问题，当然可以采用链表实现。采用数组实现时，可以找到两个特别明显的规律：
左儿子：L_Son = Parent * 2;
右儿子：R_Son = Parent * 2 + 1;
二叉堆是一颗完全填满的树，可能例外的是在底层，底层上的元素是从左到右填入，当然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用简单的基于小值的形式。主要完成的操作：1、最小值的删除操作，该操作会删除根节点，然后提升儿子节点来代替根节点，具体的实现过程中通过提升左右儿子中较小的作为父结点，依此提升直到到达最底层，这种实现方式叫做下虑法。2、数据的插入操作，插入操作可能会破坏二叉堆的结构，一般在最底层创建一个空穴，然后比较插入值与空穴父结点的值，如果大于父结点的值，那么直接插入到空穴中，如果小于父结点，则将父结点的值插入到刚创建的空穴中，在父结点所在位置上形成新的父结点，这时候再和父结点的父结点比较，具体操作如上所述，直到找到具体的插入地址。当结点个数为偶数时，在删除操作中需要注意节点是否有右儿子的情况。具体的可以参考代码中的说明。
具体的实现如下：
结构体：
#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_
#include <stdlib.h>
#include <assert.h>
#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;
}
/***********************************************************
* 下虑法实现数据的重排序操作
* 实现的方式，将子结点的两个儿子进行比较tbw，将小的提升
* 需要注意的是如何让判断节点是否一定存在右儿子
* 实现的方式主要是利用了二叉堆的特性：
* 2*pare = L_child
* 2*pare + 1 = R_child;
***********************************************************/
static void presort_BinaryHeap（BinaryHeap_handle_t heap,int hole）
{
/*这是二叉堆的特性*/
int child = hole * 2;
/*保存当前数据操作*/
int tmp = 0;
assert（heap != NULL && heap->parray != NULL）；
tmp = heap->parray[hole];
/*hold * 2 <= heap->currentSize 判断了当前结点是否为最低层*/
for（； hole * 2 <= heap->currentSize; hole = child）
{
child = hole * 2;
/*******************************
*这句代码解决是否存在右结点的问题
*并确定了那个子结点提升的问题
*******************************/
if（（child != heap->currentSize）
&& （heap->parray[child + 1] < heap->parray[child]））
child ++;
if（heap->parray[child] < tmp）
{
/*将子结点提升为父结点*/
heap->parray[hole] = heap->parray[child];
}
}
/*到达了最低的层，也就是树叶*/
heap->parray[hole] = tmp;
}
/*实现数据的下虑法实现数据的删除操作*/
int deleteMin（BinaryHeap_handle_t heap）
{
int ret = 0;
int index = 0;
assert（！isEmpty（heap））；
/*需要返回的值*/
ret = heap->parray[1];
/*将最后需要释放内存空间的值保存到第一个内存空间中*/
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;
}
测试结果：
[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
从上面的测试结果可知，基本上实现了二叉堆的基本插入、删除操作。tbw代码的关键点在于删除中的下虑和插入过程中的上虑操作。以及如何判断代码是否存在右儿子，如何充分运用二叉堆的特性。