二叉堆的C语言实现

文章正文
发布时间:2024-10-04 01:41
二叉堆的实现数据结构中如何使用,我任务主要是在操作系统中的任务优先级调度问题,当然也可以用于实现堆排序问题,比如找出数组中的第K个最小值问题,采用二叉堆能够快速的实现,今天我就采用C语言实现了一个简单的二叉堆操作,完成这些数据结构我并不知道能干什么,我就当自己在练习C语言的功底吧。逐步完成自己的代码,希望自己在知识的理解力上有一定的提高。


二叉堆是非常有特点的数据结构,可以采用简单的数组就能实现,当然链表的实现也是没有问题的,毕竟是一个二叉树问题,当然可以采用链表实现。采用数组实现时,可以找到两个特别明显的规律:

左儿子:L_Son = Parent * 2;
右儿子:R_Son = Parent * 2 + 1;

二叉堆是一颗完全填满的树,可能例外的是在底层,底层上的元素是从左到右填入,当然二叉堆可以是基于大值的排序,也可以是基于小值的排列形式,本文采用简单的基于小值的形式。主要完成的操作:1、最小值的删除操作,该操作会删除根节点,然后提升儿子节点来代替根节点,具体的实现过程中通过提升左右儿子中较小的作为父结点,依此提升直到到达最底层,这种实现方式叫做下虑法。2、数据的插入操作,插入操作可能会破坏二叉堆的结构,一般在最底层创建一个空穴,然后比较插入值与空穴父结点的值,如果大于父结点的值,那么直接插入到空穴中,如果小于父结点,则将父结点的值插入到刚创建的空穴中,在父结点所在位置上形成新的父结点,这时候再和父结点的父结点比较,具体操作如上所述,直到找到具体的插入地址。当结点个数为偶数时,在删除操作中需要注意节点是否有右儿子的情况。具体的可以参考代码中的说明。

具体的实现如下:
结构体:

本文引用地址:https://www.eepw.com.cn/article/201612/324511.htm

#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;

首页
评论
分享
Top