堆/堆排序（C/C++）

        本篇文章将会较为全面的介绍堆的概念以及实现堆两个重要算法：向上调整算法和向下调整算法。接着实现了堆排序。

        若想查看对应位置，可直接按照以下目录进行查看：

        目录

1.堆的概念及结构

2.堆的实现

2.1 堆的向上调整算法

2.2 堆的向下调整算法

2.3 堆的插入

2.4 堆的删除 

2.5 堆的实现

3.堆排序

1.堆的概念及结构

        概念：若一个关键码的集合K=\left\{ k_0,k_1,k_2,k_3,...,k_{n-1} \right\}，把它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中，并满足：sss且xxx（xxx且zzzz），则称为小堆（大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

        性质：1.堆中的某个节点的值总是不大于或不小于其父节点的值；

                   2.堆总是一颗完全二叉树；

                   3.堆中父节点的关系与孩子节点的关系为：leftchild_k=parent_{2\times i+1},rightchild_k=parent_{2\times i+2}\,\,

        堆的结构如下：

        堆的存储结构：在数据结构中，对于二叉树的存储结构一般可以分为链式存储、顺序表存储；同样，对于堆的存储我们也可以选择链式存储和顺序表存储，但我们需要从中选出最优的存储结构。对于满二叉树和完全的二叉树的顺序表存储结构对于整个顺序表都可以将其存储满，并且下标的变化便于我们在堆中添加数据和调整数据。所以我们使用顺序表来存储堆。如下：

2.堆的实现

        堆的实现主要的两个点为堆的建立和堆的调整，其中的主要思想为堆的向上调整算法和向下调整算法，具体的实现将会在下面实现。

2.1 堆的向上调整算法

        堆的向上调整发算法是实现堆的插入核心算法。

        对于堆的建立，假设我们将一组数据一个一个的加入到堆中，那么我们需要在每一个元素入堆时都要进行调整，我们将加入的元素存入到顺序表的最后，然后利用双亲结点和孩子结点之间的关系来判断是否需要调整，知道调整到根节点为止。对于此算法思想既可以使用递归算法，也可以使用循环算法，在这里我们使用循环算法，如下：

        具体的实现算法如下：

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 (child > 0) {
		//建立小堆，若建大堆，将 < 改为 >
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

2.2 堆的向下调整算法

        向下调整算法是堆删除堆顶元素的核心算法。

        向下调整算法的主要作用为：当我们需要将堆顶的元素弹出时，将整个堆进行维护，建立一个新的堆。其主要思路是将当前元素的孩子结点与双亲结点进行比较，但是此时双亲节点的孩子节点有两个，我们需要找出最合适的那一个，比如：建小堆则找出最小的孩子结点，建大堆则找出最大的孩子结点。然后将孩子结点与双亲结点进行交换，以此迭代，直到迭代到叶子结点。

        图示如下：

        以建小堆的算法为例，算法如下：

//建小堆的向下调整算法
void AdjustDown(HPDataType* a, int size, int parent) {
    //左孩子结点与双亲结点的关系
	int child = parent * 2 + 1;
    //假若右孩子比左孩子更小，则将child变量加一。child + 1 <size 用于保证不会越界
	//若建大堆，改为if ((a[child + 1] > a[child]) && (child + 1) < size)
    if ((a[child + 1] < a[child]) && (child + 1) < size) {
		++child;
	}
    //当child>=size时表示已经到达叶子结点跳出循环
	while (child<size) {
        //双亲结点大于孩子结点交换
        //若建大堆，改为if (a[parent] < a[child])
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
            //进行迭代
			parent = child;
			child = parent * 2 + 1;
			if ((a[child + 1] < a[child]) && (child + 1) < size) {
				++child;
			}
		}
        //若双亲结点不在大于孩子结点，说明已经迭代结束，不在需要继续进行迭代
		else {
			break;
		}
	}
}

2.3 堆的插入

        堆的插入就是在堆中插入元素，直接在堆的顺序存储的最后一个位置插入元素，然后调用向上调整算法，对堆进行维护。具体算法如下：

void HeapPush(Heap* php, HPDataType x) {
	assert(php);
    //判断顺序表的容量，是否需要扩容
	if (php->capacity == php->size) {
		int newCapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);
		HPDataType* tmp = (HPDataType*)realloc(php->a,newCapacity * sizeof(HPDataType));
		if (tmp == NULL) {
			perror("realloc failed:");
			exit(1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
    //调用向上调整算法
	AdjustUp(php->a, php->size);
	php->size++;
}

2.4 堆的删除 

        堆的删除就是将堆顶的元素弹出，然后使用向下调整算法对堆进行维护。具体算法如下：

void HeapPop(Heap* php) {
	assert(php);
	assert(php->a > 0);
    //将最后一个元素调换在堆顶元素位置，便于进行向下调整算法
	php->a[0] = php->a[php->size - 1];
	php->size--;
    //调用向下调整算法
	AdjustDown(php->a, php->size, 0);
}

2.5 堆的实现

        以下为堆的所有代码：

        Heap.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int HPDataType;

typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}Heap;

void HeapInit(Heap* php);
void HeapDestroy(Heap* php);
void HeapPush(Heap* php, HPDataType x);
void HeapPop(Heap* php);
HPDataType HeapTop(Heap* php);
int HeapSize(Heap* php);
bool HeapEmpty(Heap* php);

void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int size, int parent);
void Swap(HPDataType* p1, HPDataType* p2);

        Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

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

void HeapDestroy(Heap* php) {
	assert(php);
	free(php->a);
	php->capacity = php->size = 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 (child > 0) {
		//建立小堆
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

void HeapPush(Heap* php, HPDataType x) {
	assert(php);
	if (php->capacity == php->size) {
		int newCapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);
		HPDataType* tmp = (HPDataType*)realloc(php->a,newCapacity * sizeof(HPDataType));
		if (tmp == NULL) {
			perror("realloc failed:");
			exit(1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}

//建小堆的向下调整算法
void AdjustDown(HPDataType* a, int size, int parent) {
	//左孩子结点与双亲结点的关系
	int child = parent * 2 + 1;
	//假若右孩子比左孩子更小，则将child变量加一。
	if ((a[child + 1] < a[child]) && (child + 1) < size) {
		++child;
	}
	//当child>=size时表示已经到达叶子结点跳出循环
	while (child < size) {
		//双亲结点大于孩子结点交换
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			//进行迭代
			parent = child;
			child = parent * 2 + 1;
			if ((a[child + 1] < a[child]) && (child + 1) < size) {
				++child;
			}
		}
		//若双亲结点不在大于孩子结点，说明已经迭代结束，不在需要继续进行迭代
		else {
			break;
		}
	}
}

void HeapPop(Heap* php) {
	assert(php);
	assert(php->a > 0);
	php->a[0] = php->a[php->size - 1];
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

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

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

bool HeapEmpty(Heap* php) {
	assert(php);
	return php->size == 0;
}

        test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

int main() {
	int a[] = { 4,6,2,1,5,8,2,9 };
	Heap hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
		HeapPush(&hp, a[i]);
	}
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
		printf("%d ", hp.a[i]);
	}
    printf("\n");
	while (!HeapEmpty(&hp)) {
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	return 0;
}

        测试结果：

3.堆排序

        在上文中，已经较为介绍了堆的实现，现在实现堆的应用之一：堆排序。下午以降序排序为例进行介绍。

        对于堆的作用，我们在上文可以很清楚的得知，在小堆中，堆顶元素就是整个数据中最小的数据，但是对于后面的数据，并不一定呈现有序的方式排列，所以只能保证小堆的堆顶元素为最小值。所以若要将一组数据进行排序，其主要思路是先将其建堆，然后将堆顶元素放在数据最后，在将前n - 1个数据进行建堆，然后放到第n - 1个位置，以此循环递归，直至将数据排列完成。

        对于堆排序的排序原则为，降序排序为建大堆，升序排序为建小堆。以降序排序为例：当我们建立出小顶堆时，可以得出整列数据中最小的值，然后将最小值一致顺序表的最后位置，接着对前面的数据建堆，然后置换位置，以此迭代。若使用建大堆进行降序排列呢？每一次可以得到一个最大的值，然后将其放在第一个位置，对2 ~ n个位置的元素进行建堆。理论上可以，但是真正实行起来，对于第一个位置后的元素进行建堆这个步骤就会很麻烦，所以我们使用小堆进行降序排序。

        升序排序思路和上面基本一致，只有建小堆和大堆的区别。具体代码如下：

//降序排序
void HeapSort(HPDataType* a, int length) {
	// 建小堆
	for (int i = 1; i < length; i++) {
		AdjustUp(a, i);
	}
	//排序
	int end = length - 1;
	while (end > 0) {
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

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

        测试结果：

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

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

相关文章

beego代理前端web的bug

beego代理前端web的bug

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、beego代理前端web的bug总结 一、beego代理前端web的bug *报错&#xff0c;为web压缩包index.html里面的注释被错误解析&#xff0c;删掉就行 2024/02/22 10:2…
阅读更多...
解析Hadoop三大核心组件：HDFS、MapReduce和YARN

解析Hadoop三大核心组件：HDFS、MapReduce和YARN

目录 HadoopHadoop的优势 Hadoop的组成HDFS架构设计Yarn架构设计MapReduce架构设计 总结 在大数据时代&#xff0c;Hadoop作为一种开源的分布式计算框架&#xff0c;已经成为处理大规模数据的首选工具。它采用了分布式存储和计算的方式&#xff0c;能够高效地处理海量数据。Had…
阅读更多...
蛇形矩阵1

蛇形矩阵1

题目描述 把数1&#xff0c;2&#xff0c;3&#xff0c;…&#xff0c;N*N按照“蛇形1”放入N*N的矩形中&#xff0c;输出结果。 下面是N10的蛇形1的图示 输入格式 第一行1个正整数&#xff1a;N&#xff0c;范围在[1,100]。 输出格式 N行&#xff0c;每行N个整数。 输入/…
阅读更多...
docker下gitlab安装配置

docker下gitlab安装配置

一、安装及配置 1.gitlab镜像拉取 docker pull gitlab/gitlab-ce:latest2.运行gitlab镜像 docker run -d -p 443:443 -p 80:80 -p 222:22 --name gitlab --restart always --privilegedtrue -v /home/gitlab/config:/etc/gitlab -v /home/gitlab/logs:/var/log/gitlab -v …
阅读更多...
小家电—简易过零检测电路

小家电—简易过零检测电路

趁刚开工时间有空&#xff0c;总结分析下&#xff0c;在工作项目中常用过零检测电路。 图一 图二 图一在项目中较为常用&#xff0c;两个电路都是通过钳位二极管限幅产生过零脉冲信号。 过零信号高电平被钳位在5.7V&#xff0c;低电平为-0.7V 高电平&#xff1a;VCC0.7V 低电…
阅读更多...
LeetCode第七题: 整数反转

LeetCode第七题: 整数反转

题目描述 给你一个 32 位的有符号整数 x​ &#xff0c;返回将 x​ 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1]​ &#xff0c;就返回 0。 假设环境不允许存储 64 位整数&#xff08;有符号或无符号&#xff09;。 示例 …
阅读更多...
江大白 | 目标检测YOLOv9算法，重磅开源！（附论文及源码）

江大白 | 目标检测YOLOv9算法，重磅开源！（附论文及源码）

本文来源公众号“江大白”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;目标检测YOLOv9算法&#xff0c;重磅开源&#xff01;&#xff08;附论文及源码&#xff09; 以下文章来源于知乎&#xff1a;cvprLab作者&#xff1a;cvp…
阅读更多...
服务器防漏扫

服务器防漏扫

什么是漏扫&#xff1f; 漏扫是漏洞扫描的简称。漏洞扫描是一种安全测试方法&#xff0c;用于发现计算机系统、网络或应用程序中的潜在漏洞和安全弱点。通过使用自动化工具或软件&#xff0c;漏洞扫描可以检测系统中存在的已知漏洞&#xff0c;并提供相关的报告和建议&#xf…
阅读更多...
Nexus Repository Manager

Nexus Repository Manager

Nexus Repository Manager https://s01.oss.sonatype.org/#welcome https://mvnrepository.com/-CSDN博客
阅读更多...
网络安全与信创产业发展：构建数字时代的护城河

网络安全与信创产业发展：构建数字时代的护城河

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua&#xff0c;在这里我会分享我的知识和经验。&#x…
阅读更多...
二，几何相交---1，预备--(1)元素唯一性EU

二，几何相交---1，预备--(1)元素唯一性EU

如何获取数组中元素的唯一性&#xff1f; 先通过o(nlogn)的时间复杂度排序(上下界都是o(nlogn)&#xff0c;再比较相邻的两个元素即可。
阅读更多...
VScode连接远端服务器一直输入密码解决方法

VScode连接远端服务器一直输入密码解决方法

文章目录 1 关闭远程连接2打开命令面板3 输入remote-ssh: kill vs code server on host… 1 关闭远程连接 2打开命令面板 3 输入remote-ssh: kill vs code server on host… remote-ssh: kill vs code server on host… 然后一路回车(选中出问题的主机)&#xff0c;输一遍密码…
阅读更多...
LASSO算法

LASSO算法

LASSO (Least Absolute Shrinkage and Selection Operator) 是一种回归分析的方法&#xff0c;它能够同时进行变量选择和正则化&#xff0c;以增强预测准确性和模型的解释性。LASSO通过在损失函数中加入一个L1惩罚项来实现这一点。该惩罚项对系数的绝对值进行约束。 基本概念 …
阅读更多...
nginx-ingress-controller组件中Nginx的版本升级

nginx-ingress-controller组件中Nginx的版本升级

参考链接&#xff1a;https://blog.csdn.net/qq_22824481/article/details/133761302 https://blog.csdn.net/mengfanshaoxia/article/details/127155020 https://blog.csdn.net/weixin_39961559/article/details/87935873 概要 业务区k…
阅读更多...
Vue响应式状态ref()与reactive()

Vue响应式状态ref()与reactive()

1. ref()声明响应式状态 <template><!--在DOM元素调用变量时,不需要指定输出变量的value,因为Vue会帮你输出.value但是注意,这个帮助只会帮助顶级的ref属性才会被解包--><div>{{ count }}</div><div>{{ object }}</div><div>{{ arr…
阅读更多...
matlab经验模式分解的R波检测算法

matlab经验模式分解的R波检测算法

1、内容简介 略 56-可以交流、咨询、答疑 2、内容说明 略 心血管疾病是威胁人类生命的主要疾病之一&#xff0c;而心电信号&#xff08;electrocardiogram, ECG&#xff09; 则是评价心脏功能的主要依据&#xff0c;因此&#xff0c;关于心电信号检测处理的研究一直为各方所…
阅读更多...
C++ 之LeetCode刷题记录（三十四）

C++ 之LeetCode刷题记录（三十四）

&#x1f604;&#x1f60a;&#x1f606;&#x1f603;&#x1f604;&#x1f60a;&#x1f606;&#x1f603; 开始cpp刷题之旅。 目标&#xff1a;执行用时击败90%以上使用 C 的用户。 12. 整数转罗马数字 罗马数字包含以下七种字符&#xff1a; I&#xff0c; V&#xf…
阅读更多...
机器学习简单介绍

机器学习简单介绍

&#xff08;本文为简单介绍&#xff0c;内容源于网络和AI&#xff09; 当今世界,技术与创新的步伐日新月异。在各类智能技术当中,如果说有一个绝对不容忽视的关键词,那就是“机器学习”(Machine Learning)。它是人工智能领域的核心分支,使得机器获得从数据中学习、进而做出决…
阅读更多...
【JavaScript 漫游】【022】事件模型

【JavaScript 漫游】【022】事件模型

文章简介 本篇文章为【JavaScript 漫游】专栏的第 022 篇文章&#xff0c;对 JavaScript 中事件模型相关的知识点进行了总结。 监听函数 浏览器的事件模型&#xff0c;就是通过监听函数&#xff08;listener&#xff09;对事件做出反应。事件发生后&#xff0c;浏览器监听到…
阅读更多...
linux操作系统期末练习题

linux操作系统期末练习题

背景&#xff1a; 一、远程登录 1&#xff0e;利用远程登录软件&#xff0c;以用户userManager(密码123456)&#xff0c;远程登录教师计算机&#xff08;考试现场给出IP地址&#xff09;&#xff0c;只有操作&#xff0c;没有命令。 2&#xff0e;以stu班级学生个人学号后3位…
阅读更多...
最新文章

Copyright @ 2022~2023