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

相关文章

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验