数据结构 | 详解二叉树——堆与堆排序

🥝堆

堆总是一棵完全二叉树。

大堆：父节点总是大于子节点。

小堆：父节点总是小于子节点。

注意：1.同一个节点下的两个子节点并无要求先后顺序。

           2.堆可以是无序的。

🍉堆的实现

🌴深度剖析

1.父节点和子节点之间的关系

子节点=（父节点*2）+1

或者子节点=（父节点*2）+2

父节点=（子节点-1）/2

2.堆的插入HeapPush实现

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆 
void HeapPush(Heap* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		int newcapacity = 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);
		if (tmp == NULL) {
			perror("malloc fail!");
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;

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

3.堆的删除HeapPop函数的实现

函数目的：删除堆顶元素

为了避免破坏堆的整体结构，先将首尾元素进行交换，再对首元素进行向下调整，直到满足堆。最后php->size--即可删除原栈顶元素。

void HeapPop(Heap* php) {
	assert(php);
	swap(&php->a[0], &php->a[php->size - 1]);

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

🥳代码实现

Heap.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void HeapInit(Heap* php) {
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

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

void swap(int* a, int* b) {
	int tmp = *a;
	*a= *b;
	*b = tmp;
}
//小堆
void AdjustUp(HPDataType* a,int child) {
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[parent] > a[child]) {
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}


void HeapPush(Heap* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		int newcapacity = 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);
		if (tmp == NULL) {
			perror("malloc fail!");
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;

	AdjustUp(php->a,php->size);
	php->size++;
}
//从给定的子节点开始，不断向上与其父节点进行比较和可能的交换，直到达到根节点或找到一个满足最大堆性质的父节点为止。
void AdjustDown(int* a, int n, int parent) {
	assert(a);
	int child = parent * 2 + 1;
	while (child < n) {
		if (child + 1 < n && a[child] < a[child + 1]) {
			child++;
		}
		if (a[parent] < a[child]) {
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}


void HeapPop(Heap* php) {
	assert(php);
	swap(&php->a[0], &php->a[php->size - 1]);

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

HPDataType HeapTop(Heap* php) {
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

int HeapSize(Heap* php) {
	assert(php);
	return php->size;
}

int HeapEmpty(Heap* php) {
	assert(php);
	return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
int main() {
	Heap hp;
	HeapInit(&hp);
	HeapPush(&hp, 7);
	HeapPush(&hp, 6);
	HeapPush(&hp, 5);
	HeapPush(&hp, 4);
	HeapPush(&hp, 3);
	HeapPush(&hp, 2);
	HeapPush(&hp, 1);
	
	for (int i = 0; i < hp.size; i++) {
		printf("%d ", hp.a[i]);
	}
	HeapPop(&hp);
	printf("\n");
	for (int i = 0; i < hp.size; i++) {
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	printf("堆顶元素为%d\n", HeapTop(&hp));
    
	if (HeapEmpty(&hp)) {
		printf("堆不为空\n");
	}
	else {
		printf("堆为空\n");
	}

	return 0;
}

🍇堆排序

🌴深度剖析

第一步：建堆

（升序建大堆，降序建小堆）

以升序为例：

从最后一个父节点开始向前遍历，向上调整(大的上小的下）。

	//建堆：从倒数第一个父节点开始向前遍历，向下调整
	for (int i = (n-1-1)/2; i >=0 ;i--) {
		AdjustDown(a,n,i);
	}

第二步：排序

1.首尾元素交换（左图）

2.再向下调整（大的上小的下），这样调整后的堆顶元素必为调整范围内的最大值，经过下一轮的首尾元素交换后，就可以放入调整完的区域内。

while (n - 1) {
		swap(&a[0], &a[n - 1]);
		
		AdjustDown(a, n-1,0);
		n--;

🥳代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustUp(int* a, int child) {
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[parent] < a[child]) {
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
void AdjustDown(int* a, int n, int parent) {
	assert(a);
	int child = parent * 2 + 1;
	while (child < n ) {
		if (child + 1 < n  &&  a[child] < a[child + 1]) {
			child++;
		}
		if (a[parent] < a[child]) {
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}




//升序建大堆 降序建小堆
void HeapSort(int* a, int n) {
	//建堆：从倒数第一个父节点开始向前遍历，向下调整
	for (int i = (n-1-1)/2; i >=0 ;i--) {
		AdjustDown(a,n,i);
	}
	//先将首尾元素进行交换，再向下调整
	while (n - 1) {
		swap(&a[0], &a[n - 1]);
		
		AdjustDown(a, n-1,0);
		n--;
		
	}
}

int main() {
	int a[7] = { 2,6,5,1,7,4,3 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);
		for (int i = 0; i < n; i++) {
			printf("%d ",a[i]);
	}

	return 0;
}

🍉从时间复杂度角度分析建堆为何采取向下调整？

下面将分别分析向下调整算法建堆和向上调整算法建堆的区别：

向下调整建堆

假设节点数量为N,树的高度为h

第一层，2^0个节点，需要向下调整h-1层

第二层，2^1个节点，需要向下调整h-2层

第三层，2^2个节点，需要向下调整h-3层

……

第h层，2^h个节点，需要向下调整0层

可以看出：节点少的层向下调整得多，节点多的层向下调整得少

计算向下调整建堆最坏情况下合计的调整次数：

通过错位相减法可得：

因此向下调整建堆的时间复杂度为O(N）

向上调整建堆：

假设节点数量为N,树的高度为h

第一层，2^0个节点，需要向下调整0层

第二层，2^1个节点，需要向下调整1层

第三层，2^2个节点，需要向下调整2层

……

第h层，2^h个节点，需要向下调整h-1层

可以看出：节点少的层向上调整得少，节点多的层向上调整得多。

T(h)=2^1*1+2^2*2+……+2^(h-2)*(h-2)+2^(h-1)*(h-1)

同样由错位相减法可得：

T(h)=-(2^2+2^3+……+2^（h-1)）+2^h*(h-1)-2^1

整理可得：

T(N)=-N+(N+1)*(log2(N+1)-1)+1

因此向上调整建堆的时间复杂度为O（N*logN）

所以我们选择向下建堆算法明显效率更高。

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

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

相关文章

【传知代码】自监督高效图像去噪（论文复现）

【传知代码】自监督高效图像去噪（论文复现）

前言&#xff1a;在数字化时代&#xff0c;图像已成为我们生活、工作和学习的重要组成部分。然而&#xff0c;随着图像获取方式的多样化&#xff0c;图像质量问题也逐渐凸显出来。噪声&#xff0c;作为影响图像质量的关键因素之一&#xff0c;不仅会降低图像的视觉效果&#xf…
阅读更多...
python基础知识总结（第一节）

python基础知识总结（第一节）

一、python简介&#xff1a; Python是一种解释型&#xff0c;面向对象的高级语言。 Pyhton的语法和动态类型&#xff0c;以及解释性语言的本质&#xff0c;使它一跃成为多数平台上写脚本和快速开发应用的编程语言。 python语言百度百科介绍 二、Python基础语法&#xff1a;…
阅读更多...
【busybox记录】【shell指令】mkfifo

【busybox记录】【shell指令】mkfifo

目录 内容来源&#xff1a; 【GUN】【mkfifo】指令介绍 【busybox】【mkfifo】指令介绍 【linux】【mkfifo】指令介绍 使用示例&#xff1a; 创建管道文件 - 创建的时候同时指定文件权限 常用组合指令&#xff1a; 指令不常用/组合用法还需继续挖掘&#xff1a; 内容来…
阅读更多...
月赚2万佣金的AI数字人，已成为新型带货神器，完整制作教程分享

月赚2万佣金的AI数字人，已成为新型带货神器，完整制作教程分享

大家好&#xff0c;我是设计师阿威 今天和大家分享一下用AI绘画制作数字人带货的副业创收教程&#xff0c;目前数字人类型的账号在短视频平台上&#xff0c;数字人带货能力非常强&#xff01; 今天我会分享4个爆款数字人账号案例&#xff0c;深度讲解目前数字人的最新玩法。 …
阅读更多...
开源代码分享(31)-计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度

开源代码分享(31)-计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度

参考文献&#xff1a; [1]孙惠娟,刘昀,彭春华,等.计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度[J].电网技术,2021,45(09):3534-3545.DOI:10.13335/j.1000-3673.pst.2020.1720. 1.摘要 为了促进多能源互补及能源低碳化&#xff0c;提出了计及电转气协同的含碳捕集与垃…
阅读更多...
三十三、openlayers官网示例Drawing Features Style——在地图上绘制图形，并修改绘制过程中的颜色

三十三、openlayers官网示例Drawing Features Style——在地图上绘制图形，并修改绘制过程中的颜色

这篇讲的是使用Draw绘制图形时根据绘制形状设置不同颜色。 根据下拉框中的值在styles对象中取对应的颜色对象&#xff0c;new Draw的时候将其设置为style参数。 const styles {Point: {"circle-radius": 5,"circle-fill-color": "red",},LineS…
阅读更多...
Web会话管理

Web会话管理

一、会话管理的概念&#xff1a; 在人机交互时&#xff0c;会话管理是保持用户的整个会话活动的互动与计算机系统跟踪过程会话管理分类: 桌面会话管理、浏览器会话管理、Web服务器的会话管理。 二、为什么需要会话管理&#xff1f; HTTP是一种无状态协议&#xff0c;一次请…
阅读更多...
day12

day12

第一题 本题我们可以使用以下方法&#xff1a; 方法一&#xff1a; 使用hash表<元素&#xff0c;出现次数>来统计字符串中不同元素分别出现的次数&#xff0c;当某一个元素的次数大于1时&#xff0c;返回false&#xff0c;如果每个元素的出现次数都为1&#xff0c;则返回…
阅读更多...
ABB 控制柜

ABB 控制柜

1，主计算机：相当于电脑的主机，用于存放系统和数据，需要24V直流电才能工作。执行用户编写的程序，控制机器人进行响应的动作。主计算机有很多接口，比如与编程PC连接的服务网口、用于连接示教器的网口、连接轴计算机板的接口、连接安全面板的接口、不同的现场总线卡接口（比…
阅读更多...
web刷题记录（1）

web刷题记录（1）

[GXYCTF 2019]Ping Ping Ping 进入页面&#xff0c;发现有一个传入参数的框&#xff0c;目的就是为了让我们通过参数传入内容来执行代码。这里先传入本地ip&#xff0c;方便后面的ping命令运行 ls命令来查看&#xff0c;目录中的文件 传入后&#xff0c;发现目录下有flag.php,…
阅读更多...
Docker-一文详解容器通信的基础网络模式及衍生的自定义网络模式

Docker-一文详解容器通信的基础网络模式及衍生的自定义网络模式

启动容器时&#xff0c;通过-p 宿主机端口:容器端口&#xff0c;就可以通过访问宿主机端口访问到容器&#xff0c;这种原理机制是啥&#xff0c;有没有其它方式可以让宿主机和容器通信&#xff0c;以及容器与容器之间如何通信。带着这几个问题开始学习Docker的网络知识。 文章…
阅读更多...
Ai速递5.29

Ai速递5.29

全球AI新闻速递 1.摩尔线程与无问芯穹合作&#xff0c;实现国产 GPU 端到端 AI 大模型实训。 2.宝马工厂&#xff1a;机器狗上岗&#xff0c;可“嗅探”故障隐患。 3.ChatGPT&#xff1a;macOS 开始公测。 4.Stability AI&#xff1a;推出Stable Assistant&#xff0c;可用S…
阅读更多...
攀爬二叉树,发现新的美

攀爬二叉树,发现新的美

二叉树 什么是二叉树? 二叉树的基础概念? 性质? 问题? 文章目录 二叉树一、二叉树的概念(一)认识二叉树(二)二叉树的性质 二、遍历二叉树1.前序遍历2.中序遍历3.后序遍历4.层序遍历 三丶创建二叉树总结 一、二叉树的概念 (一)认识二叉树 二叉树是一种非线性的数据结构,…
阅读更多...
NSSCTF-Web题目4

NSSCTF-Web题目4

[SWPUCTF 2021 新生赛]hardrce 1、题目 2、知识点 rce&#xff1a;远程代码执行、url取反编码 3、解题思路 打开题目 出现一段代码&#xff0c;审计源代码 题目需要我们通过get方式输入变量wllm的值 但是变量的值被过滤了&#xff0c;不能输入字母和\t、\n等值 所以我们需…
阅读更多...
目标检测 | R-CNN、Fast R-CNN与Faster R-CNN理论讲解

目标检测 | R-CNN、Fast R-CNN与Faster R-CNN理论讲解

☀️教程&#xff1a;霹雳吧啦Wz ☀️链接&#xff1a;https://www.bilibili.com/video/BV1af4y1m7iL?p1&vd_sourcec7e390079ff3e10b79e23fb333bea49d 一、R-CNN R-CNN&#xff08;Region with CNN feature&#xff09;是由Ross Girshick在2014年提出的&#xff0c;在PAS…
阅读更多...
mysql中InnoDB的统计数据

mysql中InnoDB的统计数据

大家好。我们知道&#xff0c;mysql中存在许多的统计数据&#xff0c;比如通过SHOW TABLE STATUS 可以看到关于表的统计数据&#xff0c;通过SHOW INDEX可以看到关于索引的统计数据&#xff0c;那么这些统计数据是怎么来的呢&#xff1f;它们是以什么方式收集的呢&#xff1f;今…
阅读更多...
未在计算机上注册“Microsoft.Jet.OLEDB.4.0”提供程序和未在本地计算机上注册“microsoft.ACE.OLEDB.12.0”提供程序

未在计算机上注册“Microsoft.Jet.OLEDB.4.0”提供程序和未在本地计算机上注册“microsoft.ACE.OLEDB.12.0”提供程序

程序运行出现下图的错误&#xff0c; 或者下图的错误&#xff0c; 首先看一下是不是运行的程序的位数&#xff08;32/64&#xff09;不对&#xff1b; 查看系统位数的方法如下图&#xff1b;下图显示是64位操作系统&#xff1b; 如果运行的程序的位数没有问题&#xff1b; 则需…
阅读更多...
Matlab|基于PMU相量测量单元进行电力系统电压幅值和相角状态估计

Matlab|基于PMU相量测量单元进行电力系统电压幅值和相角状态估计

主要内容 程序采用三种方法对14节点和30节点电力系统状态进行评估&#xff1a; ①PMU同步相量测量单元结合加权最小二乘法&#xff08;WLS&#xff09;分析电力系统的电压幅值和相角状态&#xff1b; ②并采用牛顿-拉夫逊方法进行系统潮流计算&#xff0c;结果作为理论分…
阅读更多...
数学建模--LaTex插入表格详细介绍

数学建模--LaTex插入表格详细介绍

目录 1.插入普通的边线表格 3.三线表的插入和空格说明 3.基于复杂情况下表格的插入 1.插入普通的边线表格 &#xff08;1&#xff09;像这个右边的生成的这个比较普通的表格&#xff0c;我们是使用下面的代码实现的&#xff1a; &#xff08;2&#xff09;和插入一个一个图片…
阅读更多...
【STL】C++ stack(栈) 基本使用

【STL】C++ stack(栈) 基本使用

目录 一 stack常见构造 1 空容器构造函数&#xff08;默认构造函数&#xff09; 2. 使用指定容器构造 3 拷贝构造函数 二 其他操作 1 empty 2 size 3 top 4 push && pop 5 emplace 6 swap 三 总结 一 stack常见构造 1 空容器构造函数&#xff08;默认构造…
阅读更多...
最新文章

Copyright @ 2022~2023