二叉堆的C语言实现知识

来源:本站
导读:目前正在解读《二叉堆的C语言实现知识》的相关信息,《二叉堆的C语言实现知识》是由用户自行发布的知识型内容!下面请观看由(电工技术网 - www.9ddd.net)用户发布《二叉堆的C语言实现知识》的详细说明。
简介:二叉堆的实现数据结构中如何使用,我任务主要是在操作系统中的任务优先级调度问题,当然也可以用于实现堆排序问题,比如找出数组中的第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)

{

int i = 0;

assert(heap != NULL && heap->parray != NULL);

for(i = 1; i <= heap->currentSize; ++ i)

{

if(i %6)

printf("%dt",heap->parray[i]);

else

printf("n%dt",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:%dn",value);

value = deleteMin(pheap);

printf("pheap deleted:%dn",value);

}

print_binaryheap(&bheap);

print_binaryheap(pheap);

printf("deleteMin test successedn");

printf("****delete and free test:*******n");

delete_BinaryHeap(&bheap);

printf("Is the bheap empty ? %sn",

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

从上面的测试结果可知,基本上实现了二叉堆的基本插入、删除操作。代码的关键点在于删除中的下虑和插入过程中的上虑操作。以及如何判断代码是否存在右儿子,如何充分运用二叉堆的特性。

提醒:《二叉堆的C语言实现知识》最后刷新时间 2024-03-14 01:02:07,本站为公益型个人网站,仅供个人学习和记录信息,不进行任何商业性质的盈利。如果内容、图片资源失效或内容涉及侵权,请反馈至,我们会及时处理。本站只保证内容的可读性,无法保证真实性,《二叉堆的C语言实现知识》该内容的真实性请自行鉴别。