二叉树的顺序实现-堆

一、什么是堆

在数据结构中，堆（Heap）是一种特殊的树形数据结构，用数组存储，通常被用来实现优先队列。

堆具有以下特点：

  1. 堆是一棵完全二叉树（Complete Binary Tree），即除了最后一层外，其他层都是满的，且最后一层的节点从左到右排列。
  2. 堆中的每个节点都满足堆的性质，即父节点的值不小于（或不大于）其子节点的值，这种性质被称为堆序性（Heap Property）。
    • 最大堆（Max Heap）：父节点的值不小于其子节点的值。
    • 最小堆（Min Heap）：父节点的值不大于其子节点的值。
  3. 堆中的根节点（通常是位于最顶层的节点）是堆中的最大（或最小）元素。在最大堆中，根节点的值大于等于其子节点的值；在最小堆中，根节点的值小于等于其子节点的值。
  4. 堆不保存节点之间的具体顺序，只保证堆序性。
  5. 堆可以用数组来表示，根据节点的索引和父子节点的关系可以计算出节点之间的关系。

堆的常见操作有插入（Insert）、删除根节点（Delete Max/Min）和查找最大（或最小）元素。

堆的应用非常广泛，常见的应用包括优先队列、堆排序、图算法（如最短路径算法中的Dijkstra算法）等。通过使用堆，可以高效地在大量数据中插入、删除和获取最大（或最小）元素，时间复杂度为O(log n)。

二、堆的实现

2.1 向上调整算法

2.1.1 思路

以大堆举例：目的是要实现叶子节点要比所有的祖先节点小

  • 考虑单次：如果父节点比孩子结点小，则二者交换
  • 考虑循环：
  1. 循环体：交换之后先前的父亲节点与孩子结点的下标值互换，继续进行单次比较交换
  2. 结束条件：
    一般的情况：如果符合大堆的条件（父节点大于子节点），则可以跳出循环。
    最坏的情况：一直交换到了根节点，如果在进行下去数组就会越界，所以下标值应该>=0

2.1.2 代码

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			//下标值互换
            child = parent;
            //重新计算父亲结点的值
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2.2 向下调整算法

2.2.1 思路

以小堆举例：目的是要实现叶子节点要比所有的祖先节点大

  • 考虑单次：
  1. 先找到孩子节点中较小的结点
  2. 如果父节点比孩子结点大，则二者交换
  • 考虑循环：
  1. 循环体：交换之后先前的父亲节点与孩子结点的下标值互换，继续进行单次比较交换
  2. 结束条件：
    一般的情况：如果符合小堆的条件（父节点小于子节点），则可以跳出循环。
    最坏的情况：一直交换到了叶子节点，如果在进行下去数组就会越界，所以下标值应该<=n-1

2.2.2 代码

void AdjustDown(int* a, int n, int parent)
{
	//左孩子的下标
	int child = parent * 2 + 1;
	while (child<n)
	{
		//找到两个孩子中较小的孩子-假设法
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.3 插入

2.3.1 思路

从物理结构上讲，插入到数组的最后一个位置，然后用向上调整算法调整即可

2.3.2 代码

void HPPush(HP* php, HPDataType x)
{
	assert(php);

    //检测数组是否扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}
    //插入
	php->a[php->size] = x;
	php->size++;
    //调整
	AdjustUp(php->a, php->size - 1);
}

2.4 删除

2.4.1 思路

删除一般删除的是堆顶的元素

如果直接删除，然后用向下调整算法调整：原来的子节点会变成父节点，父节点会变成子节点。所以不可以采取此做法。

正确的做法：将堆顶元素与堆底元素交换，删除掉数组尾部元素，向下调整原数组。这样就可以规避原堆父子关系全乱的问题

2.4.2 代码

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换
    Swap(&php->a[0], &php->a[php->size - 1]);
	//删除
    php->size--;
    //调整
	AdjustDown(php->a, php->size, 0);
}

三、C语言源码汇总

3.1 heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//结构体定义
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//初始化堆
void HPInit(HP* php);
//销毁堆
void HPDestroy(HP* php);
//插入
void HPPush(HP* php, HPDataType x);
//删除
void HPPop(HP* php);
//返回堆顶元素
HPDataType HPTop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);

3.2 heap.c

#include"heap.h"

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
	// 初始条件
	// 中间过程
	// 结束条件
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	while (child < n)  // child >= n说明孩子不存在，调整到叶子了
	{
		// 找出小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// logN
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

四、堆的应用-TopK问题

4.1 分析

处理的是数据量非常大的情况下，需要知道最大/最小的某几个数的问题。

由于建堆的空间复杂度是O(N)，所以建堆的方式不可行，需要直接在数组上操作。

正确的思路：用前K个数，建一个小堆，剩下的数据跟堆顶数据比较，如果比堆顶的数据大，就替代堆顶进堆（覆盖根位置，然后向下调整）

4.2 C语言源码

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 10000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void TopK()
{
	int k;
	printf("请输入k>:");
	scanf("%d", &k);
	int* heap = (int*)malloc(sizeof(int) * k);
	if (heap == NULL)
	{
		perror("malloc fail");
		return;
	}
	const char* file = "data.txt";
	FILE* num = fopen(file, "r");
	if (num == NULL)
	{
		perror("fopen error");
		return;
	}

	// 读取文件中前k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(num, "%d", &heap[i]);
	}

	// 建K个数的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(heap, k, i);
	}

	// 读取剩下的N-K个数
	int x = 0;
	while (fscanf(num, "%d", &x) > 0)
	{
		//更新小堆的数据并进行算法排序
		if (x > heap[0])
		{
			heap[0] = x;
			AdjustDown(heap, k, 0);
		}
	}

	printf("最大前%d个数: ", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", heap[i]);
	}
	printf("\n");
}

int main()
{
	CreateNDate();

	TopK();

	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/665463.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

#centos7搭建php8+nginx环境#

#centos7搭建php8+nginx环境#

场景:为了实现上传的pdf文件转成png图片,需要搭建一个php8nginx的运行环境&#xff0c;最后安装imagic扩展 安装顺序 php-> linux-> imagemagick -> ghostscript -> imagick 一&#xff1a;安装phpnginx环境 1、安装remi扩展源 remi源是Remi repository是包含最新…
阅读更多...
Superset二次开发之更新 SECRET_KEY

Superset二次开发之更新 SECRET_KEY

SECRET_KEY 的作用 加密和签名：SECRET_KEY用于对敏感数据（如会话、cookie、CSRF令牌）进行加密和签名，防止数据被篡改。安全性：确保应用的安全性，防止跨站请求伪造（CSRF）攻击和会话劫持等安全问题。如何生成 SECRET_KEY openssl rand -base64 42 配置 SECRET_KEY 在sup…
阅读更多...
linux开发之设备树六、linux下pinctrl子系统管理设置pin管脚的复用功能（一般原厂提供）

linux开发之设备树六、linux下pinctrl子系统管理设置pin管脚的复用功能（一般原厂提供）

客户端的编写格式是固定的&#xff0c;不管哪家原厂的处理器&#xff0c;格式都是一样的 对于服务端部分是原厂提供&#xff0c;各个芯片肯定就不一样了&#xff0c;主要在于编写的格式不同 pinctrl客户端写法 使用pinctrl设置管脚复用 在kernel/arch/arm64/boot/dts/rockchi…
阅读更多...
六一见！｜Post Microsoft Build and AI Day 上海开发者日

六一见！｜Post Microsoft Build and AI Day 上海开发者日

编辑/排版&#xff1a;Alan Wang 大小朋友明天见&#xff01; 6月1日&#xff0c;Microsoft Azure & Microsoft Reactor 面向大小朋友特别推出六一特辑&#xff0c;「Post Microsoft Build and AI Day 上海开发者日」 探讨 Microsoft Build 2024 带来的最新发布&#xff0…
阅读更多...
Java常用API（三）

Java常用API（三）

一、Arrays类 1.定义 Arrays是一个用于操作数组的工具类。 2.常用方法 1.toString方法 public class Demo {public static void main(String[] args) {//toString 将数组变成字符串int[] arr {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};System.out.println(Arrays.toString(arr));…
阅读更多...
Linux目录

Linux目录

阅读更多...
绿色之国斯洛文尼亚的必游景点

绿色之国斯洛文尼亚的必游景点

斯洛文尼亚拥有多样化的景观&#xff0c;本身就是一个十分吸引人的地方。它是世界上第一个被宣布为绿色旅游目的地的国家。这里除了有优越特殊的自然特色外&#xff0c;还有被联合国教科文组织列为世界遗产的保护区&#xff0c;以及关于爱情、贵族、盐和地下神话的惊奇故事。 世…
阅读更多...
ABB机器人碰撞检测灵敏度设置

ABB机器人碰撞检测灵敏度设置

机器人的碰撞灵敏度是指机器人对碰撞事件的识别和反应能力。碰撞灵敏度取决于机器人的感知和控制系统以及其硬件结构。控制系统则负责根据感知系统的反馈信息&#xff0c;对机器人进行相应的控制和调整&#xff0c;以减少或避免碰撞。控制系统可以根据碰撞的严重程度来判断机器…
阅读更多...
8-异常与错误

8-异常与错误

8-异常与错误 1、简介2、异常处理2.1 抛出异常2.2 捕获异常2.3 匹配顺序 3、异常说明4、构造函数中的异常5、析构函数中的异常6、标准库异常 1、简介 在程序编码过程中难免会出现错误&#xff0c;主要有&#xff1a;语法错误、逻辑错误、功能错误等&#xff0c;当我们面对以上…
阅读更多...
DAQmx Connect Terminals (VI) 信号路由作用及意义

DAQmx Connect Terminals (VI) 信号路由作用及意义

DAQmx Connect Terminals是一个LabVIEW虚拟仪器&#xff08;VI&#xff09;&#xff0c;用于配置和连接数据采集系统中的物理终端或虚拟终端。这一功能在配置复杂的数据采集&#xff08;DAQ&#xff09;系统时非常重要&#xff0c;因为它允许用户在不改变硬件连接的情况下&…
阅读更多...
景源畅信数字：抖音新手如何找好自己的发布领域？

景源畅信数字：抖音新手如何找好自己的发布领域？

在短视频的浪潮中&#xff0c;抖音以其独特的魅力吸引了众多用户。对于刚踏入这个平台的新手来说&#xff0c;找到适合自己的发布领域至关重要。那么&#xff0c;如何在这个充满竞争的平台上找到自己的定位呢?接下来&#xff0c;就让我们一起来探讨这个问题。 一、明确兴趣爱好…
阅读更多...
活动选择问题（贪心法）

活动选择问题（贪心法）

目录 问题概述 实例分析 代码实现 问题概述 实例分析 求解蓄栏保留问题。农场有n头牛,每头牛会有一个特定的时间区间[b,e]在蓄栏里挤牛奶,并且一个蓄栏里任何时刻只能有一头牛挤奶。现在农场主希望知道最少蓄栏能够满足上述要求,并给出每头牛被安排的方案。对于多种可行方案…
阅读更多...
情感读本期刊万方收录综合期刊投稿

情感读本期刊万方收录综合期刊投稿

《情感读本》杂志是由国家新闻出版总署批准&#xff0c;湖北省新闻出版广电局主管&#xff0c;湖北省期刊协会主办的正规综合类期刊。《情感读本》是一本以推动和发展情感教育、素质教育、人文教育为己任&#xff0c;奉行“立足教育&#xff0c;服务社会”的办刊宗旨&#xff0…
阅读更多...
ChatGPT产品创意，直接出概念图

ChatGPT产品创意，直接出概念图

直接问&#xff0c;“给我一个创意点子” AI7号 它推荐我做一个智能家居植物管理系统&#xff0c;嗯&#xff0c;很小众的样子。直接让它出一张概念图吧。 像模像样&#xff0c;一张图太单薄了&#xff0c;再来5张。 呃...做了4张&#xff0c;下面还有每张图的说明。 你觉得怎…
阅读更多...
（奇幻森林）POLYGON - Enchanted Forest - Nature Biomes - 3D Environment Art by Synty

（奇幻森林）POLYGON - Enchanted Forest - Nature Biomes - 3D Environment Art by Synty

各种雄伟的树木，装饰着优雅简化的树叶，在头顶形成了一个天堂般的树冠，在苔藓覆盖的森林地面上投下了宁静的咒语。 每一项资产，从引人入胜的环境材料到平缓的波浪状山丘，都经过精心制作，将您带到魔法和自然融合的地方。POLYGON-魔法森林-自然生物技术为数字领域注入真正魔…
阅读更多...
实战16：基于apriori关联挖掘FP-growth算法挖掘关联规则的手机销售分析-代码+数据

实战16：基于apriori关联挖掘FP-growth算法挖掘关联规则的手机销售分析-代码+数据

直接看视频演示： 基于apriori关联挖掘关联规则的手机销售分析与优化策略 直接看结果： 这是数据展示： 挖掘结果展示： 数据分析展示：
阅读更多...
矩阵短视频：成都科成博通文化传媒公司

矩阵短视频：成都科成博通文化传媒公司

重塑内容生态与传播格局、在数字化时代&#xff0c;短视频以其独特的形式和高效的传播能力&#xff0c;迅速崛起并成为了社交媒体领域的明星。成都科成博通文化传媒公司​而“矩阵短视频”作为短视频领域的一种新兴策略&#xff0c;正以其独特的优势&#xff0c;逐渐重塑内容生…
阅读更多...
【JAVASE】String 类常用方法

【JAVASE】String 类常用方法

1、字符串构造 String类提供的构造方式很多&#xff0c;常用的有三种。 &#xff08;1&#xff09;使用常量串构造 例如&#xff1a; &#xff08;2&#xff09;直接new String对象 例如&#xff1a; &#xff08;3&#xff09;使用字符数组进行构造 例如&#xff1a; 2…
阅读更多...
20240531在飞凌的OK3588-C开发板上跑原厂的Buildroot测试ETH0接口【仅供参考】

20240531在飞凌的OK3588-C开发板上跑原厂的Buildroot测试ETH0接口【仅供参考】

20240531在飞凌的OK3588-C开发板上跑原厂的Buildroot测试ETH0接口 2024/5/31 20:28 rootrk3588-buildroot:/# ifconfig eth0 up rootrk3588-buildroot:/# ifconfig eth1 up rootrk3588-buildroot:/# ifconfig rootrk3588-buildroot:/# rootrk3588-buildroot:/# ifconfig eth1…
阅读更多...
Linux CFS调度器之周期性调度器scheduler_tick函数

Linux CFS调度器之周期性调度器scheduler_tick函数

文章目录 前言一、简介二、源码分析2.1 scheduler_tick2.2 task_tick2.3 entity_tick2.4 check_preempt_tick2.5 resched_curr 参考资料 前言 Linux内核调度器主要是主调度器和周期性调度器&#xff0c;主调度器请参考&#xff1a;Linux 进程调度之schdule主调度器 一、简介 …
阅读更多...
最新文章

Copyright @ 2022~2023