二叉堆的C言语完成

二叉堆的完结数据结构中怎么运用，我使命首要是在操作系统中的使命优先级调度问题，当然也能够用于完结堆排序问题，比方找出数组中的第K个最小值问题，选用二叉堆能够快速的完结，今日我就选用C言语完结了一个简略的二叉堆操作，完结这些数据结构我并不知道精干什么，我就当自己在操练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;