数据结构-堆排序及其复杂度计算

目录

1.堆排序

1.1 向上调整建堆

1.2 向下调整建堆

2. 两种建堆方式的时间复杂度比较

2.1 向下调整建堆的时间复杂度

2.2 向上调整建堆的时间复杂度

Topk问题

上节内容，我们讲了堆的实现，同时还包含了向上调整法和向下调整法，最后我们用堆实现了对数据的排序：

int main()
{
	HP hp;
	HeapInit(&hp);
	int arr[] = { 65,100,70,32,50,60 };
	int i = 0;
	for (i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&hp, arr[i]);
	}
	while (!HeapEmpty(&hp))
	{
		HeapDatatype top = HeapTop(&hp);
		printf("%d ", top);
		HeapPop(&hp);
	}
	return 0;
}

那以上代码能实现对数据的排序吗?

答案是可以的，但是以上方式有两个弊端：

1. 要先写一个堆，太麻烦

2. 空间复杂度+拷贝数据。

1.堆排序

上节内容中，用堆对数据进行排序，是将数据一个一个插入堆，然后再调整排序的，那我们能不能直接把数据就建成一个堆？

当然可以，建堆有两种方式：向上调整建堆、向下调整建堆。

1.1 向上调整建堆

我们先来讲向上调整建堆：

向上调整建堆其实还是插入堆的逻辑，要求前面的数据必须是一个堆，下标从1开始是因为一个数据本身就可以被看做一个堆，然后向上调整。 

下图就是我们对一个数组数据进行向上调整建堆后的结果，可以看出来，此时我们建的是一个小堆： 

现在问题来了，我们要把数据排为升序，建大堆还是建小堆好？

先说结论：升序 -- 建大堆    降序 -- 建小堆。 

假设我们要得到升序，此时又建的是小堆，那我们就把选出的最小的数据放在下标为0的位置，要想继续选出次小的数据放在下标为1的位置，就要把剩下的数据看做堆，这样堆的关系就全乱了，只能重新建堆，代价太大。

而如果我们建大堆，向下调整选出最大的数据，首尾交换，把最大的数据放在最后一个下标的位置，然后隔离最后一个数据，把其他数据看做一个堆，再向下调整选出次大的，首尾交换......直到所有的数据被排好序，此时得到的就是数据升序。

代码如下：

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

typedef int HeapDatatype;

swap(HeapDatatype* p1, HeapDatatype* p2)
{
	HeapDatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整法
void AdjustUp(HeapDatatype* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			HeapDatatype p = a[parent];
			a[parent] = a[child];
			a[child] = p;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整法
void AdjustDown(HeapDatatype* a, int n, int parent)
{
	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 = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	//向下调整得到次大数据
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

我们建的是大堆，最后得到的就是升序： 

要得到数据降序，就要建小堆，向下调整选出最小的数据，首尾交换，把最小数据放在最后一个下标的位置，隔离最后一个数据，把其他数据看做一个堆，再向下调整选出次小的数据，首尾交换......直到所有数据都被拍好序，这就得到数据降序。

代码如下：（只需将向下调整和向上调整中的'<'改为'>'即可）

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

typedef int HeapDatatype;

swap(HeapDatatype* p1, HeapDatatype* p2)
{
	HeapDatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整法
void AdjustUp(HeapDatatype* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			HeapDatatype p = a[parent];
			a[parent] = a[child];
			a[child] = p;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整法
void AdjustDown(HeapDatatype* a, int n, int parent)
{
	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 = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	//向下调整得到次小数据
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

由于我们建的是小堆，所以得到的就是数据降序： 

注意：不论是升序还是降序，数据都是从后往前放的，这样就不会使堆的关系混乱。 

1.2 向下调整建堆

我们可以看到，堆排序使用向上调整建堆，还要写两个函数：向下调整函数、向上调整函数。

那我们想用一个向下调整函数就解决问题呢？

这就需要向下调整建堆：

向下调整建堆要求根节点的左右子树都是大堆（小堆），如果左右子树不满足大堆，我们只需要确保左右子树的左右子树是大堆（小堆）即可，如果又不是，我们再往下找，所以只要使所有父节点的左右子树都是大堆（小堆）就行，那我们就倒着调整，因为叶子节点本身就是一个堆，所以不需要调整，那就从最后一个节点的父节点开始调整。

代码如下：

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

typedef int HeapDatatype;

swap(HeapDatatype* p1, HeapDatatype* p2)
{
	HeapDatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整法
void AdjustDown(HeapDatatype* a, int n, int parent)
{
	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);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

代码中int i=(n-1-1)/2是通过孩子找父亲的下标，n是数组大小，先减一得到最后一个下标，再减一除以二得到最后一个孩子的父节点。 

这就是向下调整建堆，以后我们用的都是向下调整建堆，不再使用向上调整建堆，这两种方式不仅代码量上有差距，时间复杂度上也有差距，向下调整建堆的时间复杂度更小。

2. 两种建堆方式的时间复杂度比较

2.1 向下调整建堆的时间复杂度

前文中我们知道了，向下调整建堆要保证每个父节点的左右子树都是大堆（小堆），所以我们在调整的时候是从下往上进行的，而最后一层的每个叶节点本身就可以看做一个堆，不用调整，从它们的父节点开始调整（即倒数第二层开始调整），所以时间复杂度如下：

总步数 = ∑（每一层的节点数*该节点需要调整的层数）

2.2 向上调整建堆的时间复杂度

向上调整和向下调整刚好相反，向下调整时，第h-1行的2^(h-2)个节点需向下调整1层，而向上调整时，第h-1行的2^(h-1)个节点需要向上调整h-2，向下调整是大乘小、小乘大，而向上调整时大乘大、小乘小，时间复杂度如下：

以上就是向上调整建堆和向下调整建堆的时间复杂度，那我们整个堆排序的过程的时间复杂度是多少呢？

堆排序过程中，除了建堆还有向下调整选数，当选数时，要首尾交换，交换一次，从头向下调整一次， 所以第h行的2^(h-1)个节点，每次首尾交换时都要调整(h-1)次，一共2^(h-1)*(h-1)，由此可见，选数据过程中的时间复杂度和向上调整建堆的时间复杂度保持一致，即为O(N*logN)

所以堆排序整体的时间复杂度是：建堆+选数 = O(N+N*logN)，即O(N*logN)。

Topk问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

比如：我们要找10000个数中的前K个最小的数，就把先把前K个数建小堆，然后把用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 

代码如下：

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

//Top-K问题
typedef int HeapDatatype;

swap(HeapDatatype* p1, HeapDatatype* p2)
{
	HeapDatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整法
void AdjustDown(HeapDatatype* a, int n, int parent)
{
	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 CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

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

	fclose(fin);
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc error");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}


int main()
{
	CreateNDate();
	PrintTopK(5);
	return 0;
}

关于堆排序的所有内容已经学完了，下节我们继续讲二叉树的前序、中序、后序和层序。

未完待续。。。

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

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

相关文章

Linux_磁盘管理_df命令

Linux_磁盘管理_df命令

1、df命令是用来干什么的 df的全称是disk free&#xff0c;意为“磁盘空间”。 使用df命令可以查看系统中磁盘的占用情况&#xff0c;有哪些文件系统&#xff0c;在什么位置&#xff08;挂载点&#xff09;&#xff0c;总空间&#xff0c;已使用空间&#xff0c;剩余空间等。…
阅读更多...
C++ [继承]

C++ [继承]

本文已收录至《C语言和高级数据结构》专栏&#xff01; 作者&#xff1a;ARMCSKGT 继承 前言正文继承的概念及定义继承的概念继承的定义重定义 基类和派生类对象赋值转换派生类中的默认成员函数隐式调用显示调用 继承中的友元与静态成员友元静态成员 菱形继承概念 虚继承原理继…
阅读更多...
讲座录播 | 邹磊教授：图数据库的概念和应用

讲座录播 | 邹磊教授：图数据库的概念和应用

2023年10月16日 由中国计算机学会主办的 “CCF Talk”直播间 进行了题目为 术语解读:“图计算”的内涵与应用 主题直播活动 讲座吸引7708人观看 图作为一种灵活表达复杂关联关系的数据结构&#xff0c;目前已广泛地应用于社会治理、医疗健康、电网分析、计算材料、计算育…
阅读更多...
【MySQL】事务(中)

【MySQL】事务(中)

文章目录 事务异常与产出结论手动提交 和自动提交 对 回滚的区别 事务隔离性理论如何理解隔离性&#xff1f;MySQL的隔离级别事务隔离级别的查看设置隔离级别 事务异常与产出结论 在没有启动事务之前&#xff0c;account表中存在孙权和刘备的数据 在启动事务后&#xff0c; 向 …
阅读更多...
【LIUNX】配置缓存DNS服务

【LIUNX】配置缓存DNS服务

配置缓存DNS服务 A.安装bind bind-utils1.尝试修改named.conf配置文件2.测试nslookup B.修改named.conf配置文件1.配置文件2.再次测试 缓存DNS服务器&#xff1a;只提供域名解析结果的缓存功能&#xff0c;目的在于提高数据查询速度和效率&#xff0c;但是没有自己控制的区域地…
阅读更多...
洛谷P1923 【深基9.例4】求第 k 小的数（java）

洛谷P1923 【深基9.例4】求第 k 小的数（java）

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.Scanner; //输入n个数字ai&#xff0c;输出这些数字的第k小的数。最小的数是第0小。 public cla…
阅读更多...
高级数据分析方法与模型

高级数据分析方法与模型

前言 数据思维练习不仅要熟练地掌握了分析工具&#xff0c;还要掌握大量的数据分析方法和模型。 这样得出的结论不仅具备条理性和逻辑性&#xff0c;而且还更具备结构化和体系化&#xff0c;并保证分析结果的有效性和准确性。今天从以下6个维度36种分析模型和方法逐个简略介绍…
阅读更多...
工作记录--（用HTTPS，为啥能被查出浏览记录？如何解决？）---每天学习多一点

工作记录--（用HTTPS，为啥能被查出浏览记录？如何解决？）---每天学习多一点

由于网络通信有很多层&#xff0c;即使加密通信&#xff0c;仍有很多途径暴露你的访问地址&#xff0c;比如&#xff1a; DNS查询&#xff1a;通常DNS查询是不会加密的&#xff0c;所以&#xff0c;能看到你DNS查询的观察者&#xff08;比如运营商&#xff09;是可以推断出访问…
阅读更多...
【蓝桥杯选拔赛真题67】Scratch鹦鹉学舌 少儿编程scratch图形化编程 蓝桥杯选拔赛真题解析

【蓝桥杯选拔赛真题67】Scratch鹦鹉学舌 少儿编程scratch图形化编程 蓝桥杯选拔赛真题解析

目录 scratch鹦鹉学舌 一、题目要求 编程实现 二、案例分析 1、角色分析
阅读更多...
（三）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB

（三）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB

一、七种算法&#xff08;DBO、LO、SWO、COA、LSO、KOA、GRO&#xff09;简介 1、蜣螂优化算法DBO 蜣螂优化算法&#xff08;Dung beetle optimizer&#xff0c;DBO&#xff09;由Jiankai Xue和Bo Shen于2022年提出&#xff0c;该算法主要受蜣螂的滚球、跳舞、觅食、偷窃和繁…
阅读更多...
4.CentOS7安装MySQL5.7

4.CentOS7安装MySQL5.7

CentOS7安装MySQL5.7 2023-11-13 小柴你能看到嘛 哔哩哔哩视频地址 https://www.bilibili.com/video/BV1jz4y1A7LS/?vd_source9ba3044ce322000939a31117d762b441 一.解压 tar -xvf mysql-5.7.26-linux-glibc2.12-x86_64.tar.gz1.在/usr/local解压 tar -xvf mysql-5.7.44-…
阅读更多...
高速高精运动控制，富唯智能AI边缘控制器助力自动化行业变革

高速高精运动控制，富唯智能AI边缘控制器助力自动化行业变革

随着工业大数据时代的到来&#xff0c;传统控制与决策方式无法满足现代数字化工厂对工业大数据分析与决策的需求&#xff0c;AI边缘控制器赋能现代化智慧工厂&#xff0c;实现工业智造与行业变革。 富唯智能AI边缘控制器&#xff0c;基于x86架构的IPC形态产品&#xff0c;通过…
阅读更多...
用Powershell实现：删除所有不是与.json文件重名的.jpg文件

用Powershell实现：删除所有不是与.json文件重名的.jpg文件

# 指定要搜索的目录路径 $directoryPath "C:\path\to\your\directory"# 获取该目录下的所有.jpg和.json文件 $jpgFiles Get-ChildItem -Path $directoryPath -Filter *.jpg $jsonFiles Get-ChildItem -Path $directoryPath -Filter *.json | Select-Object -Expan…
阅读更多...
对于联邦政府来说，零信任只是一个开始

对于联邦政府来说，零信任只是一个开始

今年早些时候&#xff0c;美国空军国民警卫队的一名拥有绝密安全许可的成员向社交媒体平台 Discord 泄露了国家安全文件。 据报道&#xff0c;这些文件迅速传播到其他平台&#xff0c;其中包含有关美国和北约在俄罗斯军事行动的敏感信息&#xff0c;包括有关预期武器交付的详细…
阅读更多...
2023年汽车驾驶员（高级）证考试题库及汽车驾驶员（高级）试题解析

2023年汽车驾驶员（高级）证考试题库及汽车驾驶员（高级）试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年汽车驾驶员&#xff08;高级&#xff09;证考试题库及汽车驾驶员&#xff08;高级&#xff09;试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;…
阅读更多...
软件测试开发环境、测试环境、准生产环境、生成环境

软件测试开发环境、测试环境、准生产环境、生成环境

在一个项目开发到发布的整个过程中&#xff0c;会使用到很多个环境进行测试和运行项目。最基本的开发环境、测试环境、准生产环境、生成环境 一、开发环境 开发环境顾名思义就是我们程序猿自己把项目放到自己的电脑上&#xff0c;配置好以后&#xff0c;跑起来项目&#xff0…
阅读更多...
SpringCloud微服务：服务拆分

SpringCloud微服务：服务拆分

不同的数据库之间&#xff0c;如何共同调用&#xff1f;接下来讲讲两个数据库之间如何交互 1、微服务需要根据业务模块拆分&#xff0c;做到单一职责,不要重复开发相同业务 2、微服务可以将业务暴露为接口&#xff0c;供其它微服务使用 3、不同微服务都应该有自己独立的数据库…
阅读更多...
（四）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB

（四）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB

一、七种算法&#xff08;DBO、LO、SWO、COA、LSO、KOA、GRO&#xff09;简介 1、蜣螂优化算法DBO 蜣螂优化算法&#xff08;Dung beetle optimizer&#xff0c;DBO&#xff09;由Jiankai Xue和Bo Shen于2022年提出&#xff0c;该算法主要受蜣螂的滚球、跳舞、觅食、偷窃和繁殖…
阅读更多...
【赠书第4期】机器学习与人工智能实战：基于业务场景的工程应用

【赠书第4期】机器学习与人工智能实战：基于业务场景的工程应用

文章目录 前言 1 机器学习基础知识 2 人工智能基础知识 3 机器学习和人工智能的实战案例 4 总结 5 推荐图书 6 粉丝福利 前言 机器学习与人工智能是当前最热门的领域之一&#xff0c;也是未来发展的方向。随着科技的不断进步&#xff0c;越来越多的企业开始关注和投入机…
阅读更多...
哈希的介绍及开散列和闭散列的实现(c++)

哈希的介绍及开散列和闭散列的实现(c++)

本文主要对哈希的相关知识进行一定的介绍&#xff0c;并对哈希中结构的闭散列和开散列进行一定的介绍和部分功能的实现。 目录 一、哈希概念 二、哈希冲突 三、哈希函数 1. 直接定址法--(常用) 2. 除留余数法--(常用) 3. 平方取中法 4. 折叠法 5. 随机数法 6. 数学分析…
阅读更多...
最新文章

Copyright @ 2022~2023