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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件