【数据结构】（C语言）：堆（二叉树的应用）

news/2024/7/8 5:36:41 标签: 数据结构, c语言

堆：

  • 此处堆为二叉树的应用，不是计算机中用于管理动态内存的堆。
  • 形状是完全二叉树。
  • 堆分两种：最大堆，最小堆。
  • 最大堆：每个节点比子树所有节点的数值都大，根节点为最大值。
  • 最小堆：每个节点比子树所有节点的数值都小，根节点为最小值。
  • 左右节点的数值没有顺序要求，但有左子节点才能有右子节点。
  • 一般用数组实现堆。最小堆可以实现优先队列。

注：完全二叉树：每个节点最多2个节点，倒数第二层级（含）之前层级的所有节点都有元素，最后一层级从左到右依次有元素（中间不能断）。

子树：节点及其所有子节点形成子树。（即节点，左右子节点，左右子节点的左右子节点，。。。）

根节点：没有父节点。

兄弟节点：其父节点是同一个节点。

父子节点在数组中的索引号
节点索引号（根节点为0）
节点x
父节点（x-1）// 2
左兄弟节点（右节点才有）x - 1
右兄弟节点（左节点才有）x + 1
左子节点2x + 1
右子节点2x + 2

C语言实现：（使用数组实现最小堆）

创建堆（结构体数据类型）：记录数组地址和元素个数

// 堆（结构体数据类型）
typedef struct Heap
{
	int *p;			// 记录数组地址
	int n;			// 记录元素个数
} Heap;             // 别名

 （函数）堆初始化：

// 堆初始化
void init(Heap *heap, int length)
{
	heap->p = (int *)malloc(length * sizeof(int));    // 分配内存空间
	if(heap->p == NULL)
	{
		perror("Memory allocation failed");
		exit(-1);
	}
	heap->n = 0;            // 元素个数，初始化为0
}

 创建堆变量，并初始化

Heap heap;         // 创建堆变量
init(&heap, 8);    // 设置数组最大元素个数为8

添加元素：

1、先在末尾添加元素。

2、（向上调整）与父节点比较大小，若小于父节点，与父节点交换位置，直到开头位置（根节点，数组第一个元素）。

（注：子节点索引号为x，父节点索引号为(x-1)//2）

void add(Heap *heap, int data)		// add a element to the heap
{
	// 往末尾添加元素
	heap->p[heap->n] = data;
	// (向上调整) 与父节点比较，小于父节点的值，与父节点交换位置
	int cur = heap->n;
	while(cur > 0)
	{
		int parent = ceil((cur - 1) / 2);
		if(heap->p[parent] > data)
		{
			heap->p[cur] = heap->p[parent];
			heap->p[parent] = data;
			cur = parent;
		}
		else break;
	}
    // 每添加一个元素，元素个数+1
	heap->n++;
}

删除（根节点）：

1、记录根节点（数组第一个元素）和末尾节点（数组最后一个元素）。

2、末尾节点的值换到根节点位置，元素个数-1。

3、（向下调整）从根节点开始，依次与左右子节点比较大小，数值小的是父节点，直到比对到末尾。

（注：父节点索引号为x，左子节点索引号为2x+1，右子节点索引号为2x+2）

int delete(Heap *heap)			// delete root from the heap
{
	if(heap->n == 0) return -1;    // 空树
	heap->n--;                     // 每删除一次根节点，元素个数-1
	int root = heap->p[0], enddata = heap->p[heap->n];
	heap->p[0] = enddata;	       // 末尾元素换到第一个位置
	// (向下调整) 与左右子节点比较，若子节点小，与较小子节点交换位置
	int cur = 0;
	while(cur <= heap->n)
	{
		int left = cur * 2 + 1, right = cur * 2 + 2, minchild;
		if(left > heap->n) break;				// 没有左子节点
		if(right > heap->n) minchild = left;	// 没有右子节点，有左子节点
		else									// 左右子节点都有的情况
		{
			// 左右子节点比较，找到较小子节点
			if(heap->p[right] < heap->p[left]) minchild = right;
			else minchild = left;
			// 父节点与较小子节点比较，若子节点小，与子节点交换位置
			if(heap->p[minchild] < enddata)
			{
				heap->p[cur] = heap->p[minchild];
				heap->p[minchild] = enddata;
				cur = minchild;
			}
			else break;
		}
	}
	return root;
}

获取根节点：（数组第一个元素）

int getroot(Heap *heap)			// get the root from the heap
{
	if(heap->n == 0)
	{
		printf("Empty heap\n");
		exit(-1);
	}
	return heap->p[0];
}

遍历堆：（类似广度遍历二叉树）

每个节点比子树的所有节点都小，但左右节点没有顺序要求。

void traverse(Heap *heap)		// show element one by one (like breadth traverse the tree)
{
	if(heap->n == 0) return ;

	printf("elements(%d): ", heap->n);
	for(int k = 0; k < heap->n; k++)
	{
		printf("%d  ", heap->p[k]);
	}
	printf("\n");
}

清空堆：

释放数组内存空间，指向数组的指针指向NULL，元素个数为0。

void clear(Heap *heap)		// clear the heap (free memory space of the array)
{
	free(heap->p);          // 释放数组内存空间
	heap->p = NULL;         // 指针指向NULL，避免野指针
	heap->n = 0;            // 元素个数为0
}

 

完整代码：（heap.c）

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

/* structure */
typedef struct Heap
{
	int *p;			// memory address of the heap (array)
	int n;			// the number of the heap
} Heap;

/* function prototype */
void init(Heap *, int);		// heap initialization
void add(Heap *, int);		// add a element to the heap
int delete(Heap *);			// delete root from the heap
int getroot(Heap *);		// get the root from the heap
void traverse(Heap *);		// show element one by one (likely breadth traverse the tree)
void clear(Heap *);			// clear the heap (free memory space of the array)

/* main function */
int main(void)
{
	Heap heap;
	init(&heap, 8);
	printf("length: %d\n", heap.n);

	add(&heap, 5);	
	printf("root(the minimum): %d\n", getroot(&heap));
	traverse(&heap);
	add(&heap, 8);	
	add(&heap, 3);	
	add(&heap, 9);	
	add(&heap, 2);
	printf("root(the minimum): %d\n", getroot(&heap));
	traverse(&heap);

	delete(&heap);	
	printf("root(the minimum): %d\n", getroot(&heap));
	traverse(&heap);
	delete(&heap);	
	printf("root(the minimum): %d\n", getroot(&heap));
	traverse(&heap);
	
	clear(&heap);
	printf("length: %d\n", heap.n);
	printf("root(the minimum): %d\n", getroot(&heap));
	return 0;
}

/* subfunction */
void init(Heap *heap, int length)		// heap initialization
{
	heap->p = (int *)malloc(length * sizeof(int));
	if(heap->p == NULL)
	{
		perror("Memory allocation failed");
		exit(-1);
	}
	heap->n = 0;
}

void add(Heap *heap, int data)		// add a element to the heap
{
	// add a element to the end of the heap
	heap->p[heap->n] = data;
	// (adjust up) compair with parent,if smaller than parent, change the position
	int cur = heap->n;
	while(cur > 0)
	{
		int parent = ceil((cur - 1) / 2);
		if(heap->p[parent] > data)
		{
			heap->p[cur] = heap->p[parent];
			heap->p[parent] = data;
			cur = parent;
		}
		else break;
	}
	heap->n++;
}

int delete(Heap *heap)			// delete root from the heap
{
	if(heap->n == 0) return -1;
	heap->n--;
	int root = heap->p[0], enddata = heap->p[heap->n];
	heap->p[0] = enddata;	// put the last element to the first position
	// (adjust down) compair with left and right child, minimun is parent
	int cur = 0;
	while(cur <= heap->n)
	{
		int left = cur * 2 + 1, right = cur * 2 + 2, minchild;
		if(left > heap->n) break;				// no left child
		if(right > heap->n) minchild = left;	// have left child, no right child
		else									// have left child and right child
		{
			// compair left child and right child, find smaller one
			if(heap->p[right] < heap->p[left]) minchild = right;
			else minchild = left;
			// smaller child compair with parent,if child is the smallest, change
			if(heap->p[minchild] < enddata)
			{
				heap->p[cur] = heap->p[minchild];
				heap->p[minchild] = enddata;
				cur = minchild;
			}
			else break;
		}
	}
	return root;
}

int getroot(Heap *heap)			// get the root from the heap
{
	if(heap->n == 0)
	{
		printf("Empty heap\n");
		exit(-1);
	}
	return heap->p[0];
}

void traverse(Heap *heap)		// show element one by one (like breadth traverse the tree)
{
	if(heap->n == 0) return ;

	printf("elements(%d): ", heap->n);
	for(int k = 0; k < heap->n; k++)
	{
		printf("%d  ", heap->p[k]);
	}
	printf("\n");
}

void clear(Heap *heap)		// clear the heap (free memory space of the array)
{
	free(heap->p);
	heap->p = NULL;
	heap->n = 0;
}

编译链接： gcc -o heap heap.c

执行可执行文件： ./heap

 


http://www.niftyadmin.cn/n/5536558.html

相关文章

C语言 指针和数组——指针的算术运算

C语言 指针和数组——指针的算术运算

目录 指针的算术运算 指针加上一个整数 指针减去一个整数 指针相减 指针的关系比较运算 小结 指针的算术运算 指针加上一个整数 指针减去一个整数 指针相减 指针的关系比较运算 小结  指针变量 – 指针类型的变量&#xff0c;保存地址型数据  指针变量与其他类型…
阅读更多...
ubuntu软件源的两种格式和环境变量

ubuntu软件源的两种格式和环境变量

1. ubuntu的/etc是什么目录&#xff1f; 在Ubuntu操作系统中&#xff0c;/etc/是一个特殊的目录&#xff0c;它包含系统的配置文件。这些配置文件用于设置各种系统和应用程序的参数和选项。 一般来说&#xff0c;用户可以在这个目录下找到各种重要的配置文件&#xff0c;如网络…
阅读更多...
Java增加线程后kafka仍然消费很慢

Java增加线程后kafka仍然消费很慢

文章目录 一、问题分析二、控制kafka消费速度属性三、案例描述 一、问题分析 Java增加线程通常是为了提高程序的并发处理能力&#xff0c;但如果Kafka仍然消费很慢&#xff0c;可能的原因有&#xff1a; 网络延迟较大&#xff1a;如果网络延迟较大&#xff0c;即使开启了多线…
阅读更多...
腾讯课堂即将停止服务？来试试这款开源的知识付费系统

腾讯课堂即将停止服务？来试试这款开源的知识付费系统

项目介绍 本系统基于ThinkPhp5.0layuiVue开发,功能包含在线直播、付费视频、付费音频、付费阅读、会员系统、分销系统、拼团活动、直播带货、直播打赏、商城系统等。能够快速积累客户、会员数据分析、智能转化客户、有效提高销售、吸引流量、网络营销、品牌推广的一款应用&…
阅读更多...
【Linux】Linux常用指令合集精讲，一篇让你彻底掌握(万字真言)

【Linux】Linux常用指令合集精讲，一篇让你彻底掌握(万字真言)

文章目录 一、文件与目录操作1.1 ls - 列出目录内容1.2 cd - 切换目录1.3 pwd - 显示当前目录1.4 mkdir - 创建目录1.5 rmdir - 删除空目录1.6 rm - 删除文件或目录1.7 cp - 复制文件或目录1.8 mv - 移动或重命名文件或目录1.9 touch - 创建空文件或更新文件时间戳 二、文件内容…
阅读更多...
Java 项目的构建工具 Maven

Java 项目的构建工具 Maven

Maven 一、Maven 简介二、Maven 安装配置1、Maven 下载安装2、Maven 配置 三、IDEA 集成 Maven四、Maven 依赖管理1、依赖配置2、依赖传递3、依赖范围4、生命周期 五、Maven 高级特性1、分模块设计与开发2、Maven 继承3、Maven 版本管理4、Maven 聚合5、私服 一、Maven 简介 M…
阅读更多...
R迅速切换目录 -R语言002

R迅速切换目录 -R语言002

实用小操作系列 R定位当前目录 getwd() [1] "/data/Rprofile1" #当前工作目录&#xff0c;因为他读取文件都是相对路径&#xff0c;进当前目录&#xff0c;一般不考虑绝对路径&#xff0c;写代码容易乱呀&#xff0c;切目录最简单完善 R切换工作目录 setwd(&q…
阅读更多...
IT项目管理具体都管哪些内容？

IT项目管理具体都管哪些内容？

项目启动&#xff1a; 定义项目的目的和目标。确定项目范围。获取项目批准和资源承诺。 范围管理&#xff1a; 明确项目要做什么&#xff0c;不做什么。制定范围说明书。控制范围变更。 时间管理&#xff1a; 规划项目时间线和里程碑。制定详细的项目进度计划。监控和控制项目…
阅读更多...
最新文章

Copyright @ 2022~2023