C语言数据结构堆排序、向上调整和向下调整的时间复杂度的计算、TopK问题等的介绍

本文主要是介绍C语言数据结构堆排序、向上调整和向下调整的时间复杂度的计算、TopK问题等的介绍,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、堆排序
    • 1. 排升序
      • (1). 建堆
      • (2). 排序
    • 2. 拍降序
      • (1). 建堆
      • (2). 排序
  • 二、建堆时间复杂度的计算
    • 1. 向上调整时间复杂度
    • 2. 向下调整时间复杂度
  • 三、TopK问题
  • 总结


前言

C语言数据结构堆排序、向上调整和向下调整的时间复杂度的计算、TopK问题等的介绍


一、堆排序

排列一个一维数组,可以通过两个步骤进行排序。

  1. 建堆(大根堆或小根堆)
  2. 堆排序(通过向下或者向上调整排序)’

需要注意的是 堆排序排升序则建大堆,排降序则建小堆。

1. 排升序

(1). 建堆

这里建堆采用向下调整建堆,因为向上调整建堆的时间复杂度比向下调整建堆的时间复杂度大。可参考二。

  • 向下调整建堆,从最后一个叶子节点的父节点开始调整。
// 向下调整 按大根堆调整
void AdjustDown(HPDataType* 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[child] > a[parent]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 排升序 建大堆
void HeapSort(int* arr, int n)
{int i = 0;// 建堆---向下调整建堆for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}
}
  • (n-1)是找到最后一个叶子节点,(n-1-1)/2找到最后一个叶子节点的双亲节点,然后向下调整。

(2). 排序

  • 排序的思想:
    和删除堆顶的元素的思想一样。
  1. 已经建好了大堆,所以先交换根元素和最后一个叶子节点元素。此时最后一个叶子节点是最大值。
  2. 将此时除了最后一个叶子节点元素看成一个堆,并将此时的根元素向下调整。
  3. 再继续交换根元素和此时最后一个叶子结点元素,重复以上过程。即可达到排序效果。
// 排升序 建大堆
void HeapSort(int* arr, int n)
{int i = 0;// 建堆---向下调整建堆for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}// 排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}int main()
{int arr[10] = { 2,3,1,9,5,7,8,6,4, 0 };HeapSort(arr, 10);int i = 0;for (i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

效果如下:
在这里插入图片描述

2. 拍降序

(1). 建堆

  • 排降序,建小堆
  • 向下调整建小堆,向下调整的时间复杂度比向上调整时间复杂度低
// 向下调整 按小根堆调整
void AdjustDown(HPDataType* 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[child] < a[parent]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 拍降序,建小堆
void HeapSort(int* arr, int n)
{int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}
}

(2). 排序

  • 排序的思想:
    和删除堆顶的元素的思想一样。
  1. 已经建好了小堆,所以先交换根元素和最后一个叶子节点元素。此时最后一个叶子节点是最小值。
  2. 将此时除了最后一个叶子节点元素看成一个堆,并将此时的根元素向下调整。
  3. 再继续交换根元素和此时最后一个叶子结点元素,重复以上过程。即可达到排序效果。
// 拍降序,建小堆
void HeapSort(int* arr, int n)
{int i = 0;// 建堆---- 向下调整建堆for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}// 排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}}int main()
{int arr[10] = { 2,3,1,9,5,7,8,6,4, 0 };HeapSort(arr, 10);int i = 0;for (i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

效果如下:
在这里插入图片描述

注意拍升序和拍降序的向下调整函数是不一样的

二、建堆时间复杂度的计算

  • 建堆事实上是模拟堆中插入数据,并向上或向下调整。
  • 所以建堆时间复杂度的计算本质上是向上或者向下调整的时间复杂度

注意: 堆是完全二叉树,这里用满二叉树来近似计算,因为时间复杂度计算的是量级,多或少节点不影响。

1. 向上调整时间复杂度

见图示:
1.
在这里插入图片描述

在这里插入图片描述

2. 向下调整时间复杂度

见图示:
1.
在这里插入图片描述

在这里插入图片描述

三、TopK问题

在非常大的数字中找到前K个

  • 由于没有数据,先随机生成10000个数据写入文件中
  • 然后建K个数据的小堆
  • 剩余n-k个数据依次与小堆根元素比较,若大于根元素则入堆,并向下调整,若不大于根元素,则继续找下一个,知道文件读完。
void PrintfTopK(const char* file, int k)
{int* topk = (int*)malloc(sizeof(int)* k);if (topk == NULL){perror("PrintfTopK malloc");return;}// 以读的形式打开文件FILE* pfout = fopen(file, "r");if (pfout == NULL){perror("PrintfTopK fopen");return;}int i = 0;// 读出前K个数for (i = 0; i < k; i++){fscanf(pfout, "%d", &topk[i]);}// 建堆for (i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, k, i);}// 剩余n - k 个数分别于根元素比较int val = 0;int ret = fscanf(pfout, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(pfout, "%d", &val);}for (i = 0; i < k; i++){printf("%d ", topk[i]);}free(topk);fclose(pfout);
}void CreateNData()
{int n = 10000;const char* file = "data.txt";FILE* pfin = fopen(file, "w");if (pfin == NULL){perror("TestTopK fopen");return;}int i = 0;for (i = 0; i < n; i++){int x = rand() % 10000;fprintf(pfin, "%d\n", x);}fclose(pfin);
}int main()
{srand((unsigned int)time(NULL));CreateNData();PrintfTopK("data.txt", 10);return 0;
}
  • 其中的向下调整都是按小根堆向下调整。可参考一、二内容

效果如下:
在这里插入图片描述


总结

C语言数据结构堆排序、向上调整和向下调整的时间复杂度的计算、TopK问题等的介绍

这篇关于C语言数据结构堆排序、向上调整和向下调整的时间复杂度的计算、TopK问题等的介绍的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1015179

相关文章

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命