【数据结构】堆排序和top-K问题

堆的实现源码

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <assert.h>
typedef struct Heap
{int* a;int size;int capacity;
}Heap;
void HeapInit(Heap* st)
{st->a = NULL;st->capacity = 0;st->size = 0;
}
void swap(int* str1, int* str2)
{int tmp = *str1;*str1 = *str2;*str2 = tmp;}
void Adjustup(int* 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* st, int x)
{if (st->capacity == st->size){int newcapcity = st->capacity == 0 ? 4 : st->capacity * 2;int* tmp = (int*)realloc(st->a, newcapcity * sizeof(int));if (tmp == NULL){perror("realloc fail");}st->a = tmp;st->capacity = newcapcity;}st->a[st->size] = x;st->size++;Adjustup(st->a, st->size - 1);
}
void Heapprint(Heap* st)
{for (int i = 0; i < st->size; i++){printf("%d ", st->a[i]);}}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
bool HeapEmpty(Heap* st)
{assert(st);if (st->size == 0){return true;}else{return false;}}
int HeapSize(Heap* st)
{assert(st);return st->size;
}
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));swap(&hp->a[0], &hp->a[hp->size - 1]);hp->size--;AdjustDown(hp->a, hp->size, 0);
}
void HeapDestroy(Heap* st)
{assert(st);free(st->a);st->a = NULL;st->size = 0;st->capacity = 0;
}
int HeapTop(Heap* st)
{assert(st);assert(!HeapEmpty(st));return st->a[0];}

使用堆结构实现堆排序

void HeapSort(int* a, int n)
{Heap hp;HeapInit(&hp);//初始化堆
for (int i = 0; i < 10; i++)
{HeapPush(&hp, a[i]);//堆中插入元素，每次插入做向上调整.保证堆是小堆
}while (!HeapEmpty(&hp))//如果堆不为空的话
{int top=HeapTop(&hp);//每次取堆顶数据为最小printf("%d ", top);HeapPop(&hp);//删除堆顶元素时，重新调整堆，使其还是小堆}}

主函数

int main()
{int arr[10] = { 52,85,74,46,23,14,65,25,32,78 };HeapSort(arr, 10);}

编译运行

在这里插入图片描述

如果用上述方法写堆的话，还必须写一个堆的结构，特别麻烦.

排序方法2

1.排列升序

我们可以直接使用向上调整和向下调整建堆，实质上的堆只是数组，向上调正和向下调整只是操作下标而已.
排列升序我们应该创建大堆还是小堆，如果不仔细想一想的话，可能是创建一个小堆，然后依次取对顶元素，但是如果依次取堆顶元素的话，剩下的元素就不能构成一个堆，堆的关系就全乱了.如下图所示.取出堆顶的小元素.重新排列的话.
在这里插入图片描述
因此我们如果要排升序的话，就创建大堆，我们既可以用向上调整创建大堆，也可以用向下调整创建大堆

向下调整创建大堆

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] >a[child])//这里要选大的孩子和父亲交换{child++;}if (a[child] >a[parent])//比父亲大的孩子向上走.{swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{Heap hp;for (int i = (n - 1 - 1) / 2; i >=0; --i)//从最后一个非子叶节点开始走.直到堆顶的元素{AdjustDown(a, n, i);}}int main()
{Heap hp;//createdata();//printtopK(10);int arr[10] = { 52,85,74,46,23,14,65,25,32,78 };HeapSort(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}}

向上调整创建大堆

void Adjustup(int* 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 HeapSort(int* a, int n)
{Heap hp;for (int i = 1; i < n; i++){Adjustup(a, i);}//for (int i = (n - 1 - 1) / 2; i >=0; --i)//{//	AdjustDown(a, n, i);//}}int main()
{Heap hp;//createdata();//printtopK(10);int arr[10] = { 52,85,74,46,23,14,65,25,32,78 };HeapSort(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}}

创建的大堆
在这里插入图片描述

在这里插入图片描述

然后将创建好的大堆进行排序
修改后的堆排序

void HeapSort(int* a, int n)
{Heap hp;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;
}
}

在这里插入图片描述

排降序

由排升序创建大堆，则排降序创建小堆，创建小堆既可以用向上调整法，还可以使用向下调整

向下调整创建小堆

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] <a[child]){child++;}if (a[child] <a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{Heap hp;for (int i = (n - 1 - 1) / 2; i >=0; --i){AdjustDown(a, n, i);}}int main()
{Heap hp;//createdata();//printtopK(10);int arr[10] = { 52,85,74,46,23,14,65,25,32,78 };HeapSort(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}}

向上调整创建小堆

void Adjustup(int* 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 HeapSort(int* a, int n)
{Heap hp;for (int i = 1; i < n; i++){Adjustup(a, i);}//for (int i = (n - 1 - 1) / 2; i >=0; --i)//{//	AdjustDown(a, n, i);//}}int main()
{Heap hp;//createdata();//printtopK(10);int arr[10] = { 52,85,74,46,23,14,65,25,32,78 };HeapSort(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}}

将创建好的小堆进行排序

void Adjustup(int* 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 HeapSort(int* a, int n)
{Heap hp;for (int i = 1; i < n; i++){Adjustup(a, i);}//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()
{Heap hp;//createdata();//printtopK(10);int arr[10] = { 52,85,74,46,23,14,65,25,32,78 };HeapSort(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}}

总结：创建大堆或者小堆都可以用向上调整和向下调整，如果创建大堆对应的调整必须修改成孩子大于父亲进行交换，这样的话就可以把大数放在堆顶上.，如果创建小堆的话，孩子小于父亲的话，在进行交换，值得注意的是，创建大堆时，并且使用向下调整的话，需要将孩子的下标落在左右孩子较大的孩子身上.创建小堆时，需要将孩子的下标落在左右孩子较小的身上.

top-K问题

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

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

找最大的10个

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include <stdlib.h>//srand头文件
#include <time.h>//time头文件
void swap(int* str1, int* str2)//交换两个数据的值
{int tmp = *str1;*str1 = *str2;*str2 = tmp;}void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
void createdata()
{int n = 10000;srand((unsigned int)time(NULL));//产生随机数种子FILE* fp = fopen("xa.txt", "w");//以写的方式打开文件if (fp == NULL){perror("fopen fail");return;}for (int i = 0; i < 10000; i++)//产生10000个随机数，{int x = rand()%10000;//并且每一个随机数都是小于10000.fprintf(fp,"%d\n",x);//将其写入文件中，并且换行	}fclose(fp);
}
void printtopk(int k)
{FILE* fp = fopen("xa.txt", "r");if (fp == NULL){perror("fopen fail");return;}int* kminheap = (int*)malloc(sizeof(int) * k);//动态申请10个空间大小if (kminheap == NULL){perror("malloc fail");}for (int i = 0; i < k; i++){fscanf(fp,"%d",&kminheap[i]);//先读取文件前10个数据} for (int i = (k - 1 - 1) / 2; i >= 0; i--)//向下调整为小堆，因为选最大的10个要排小堆{AdjustDown(kminheap, k, i);}int val = 0;while (!feof(fp))//文件中剩下的数据需要与小堆中堆顶元素比较，如果大于堆顶元素，就把堆顶元素更新{fscanf(fp,"%d", &val);//读取文件中的数据到val中if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k,0);//比堆顶最小的大，就入堆，然后将堆顶元素向下调整，调整后，还需要保证是小堆。}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}}int main()
{createdata();printtopk(10);}

在这里插入图片描述

找最小的10个

需要创建大堆

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int* str1, int* str2)
{int tmp = *str1;*str1 = *str2;*str2 = tmp;}void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
void createdata()
{int n = 10000;srand((unsigned int)time(NULL));FILE* fp = fopen("xa.txt", "w");if (fp == NULL){perror("fopen fail");return;}for (int i = 0; i < 10000; i++){int x = rand()%10000;fprintf(fp,"%d\n",x);}fclose(fp);
}
void printtopk(int k)
{FILE* fp = fopen("xa.txt", "r");if (fp == NULL){perror("fopen fail");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");}for (int i = 0; i < k; i++){fscanf(fp,"%d",&kminheap[i]);} for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}int val = 0;while (!feof(fp)){fscanf(fp,"%d", &val);if (val <kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k,0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}}int main()
{createdata();printtopk(10);}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

R语言 复习 习题图片

R语言 复习 习题图片

这是日天土申哥不知道从哪淘来的R语言复习知识点图片&#xff0c;大部分内容都是课后习题的答案 加油吧&#xff0c;骚年&#xff0c;考个好分数
阅读更多...
董事长孙进任职资格获批，盛京银行坎坷向前

董事长孙进任职资格获批，盛京银行坎坷向前

11月6日&#xff0c;国家金融监管总局行政许可信息显示&#xff0c;盛京银行&#xff08;HK:02066&#xff09;董事长孙进的任职资格已于近日获准。 作为东北地区成立最早、规模最大的总部银行&#xff0c;盛京银行近年来的发展之路颇为坎坷&#xff0c;在经历了大规模的管理层…
阅读更多...
2023最新版JavaSE教程——第1天：Java语言概述

2023最新版JavaSE教程——第1天：Java语言概述

目录 一、抽丝剥茧话Java1.1 当前大学生就业形势1.2 IT互联网是否依旧靠谱1.3 IT行业岗位分析1.4 软件开发之Java开发1.5 到底多少人在用Java 二、计算机的硬件与软件2.1 计算机组成&#xff1a;硬件软件2.2 CPU、内存与硬盘2.3 输入设备&#xff1a;键盘输入 三、软件相关介绍…
阅读更多...
单链表的建立(头插法、尾插法)(数据结构与算法)

单链表的建立(头插法、尾插法)(数据结构与算法)

如果要把很多个数据元素存到一个单链表中&#xff0c;如何操作&#xff1f; 1.初始化一个单链表 2. 每次取一个数据元素&#xff0c;插入到表尾/表头 1. 尾插法建立单链表 尾插法建立的单链表元素顺序与输入数据集合的顺序相同&#xff0c;即按照输入数据的顺序排列。 使用尾插…
阅读更多...
03运算符综合

03运算符综合

03 3.1.1算数运算符 3.1.2赋值运算符 3.1.3比较&#xff08;关系&#xff09;运算符 3.1.4逻辑运算符 3.1.5位运算符 3.2运算符的优先级 3.3条件表达式
阅读更多...
web3 React dapp项目通过事件从区块链中拿到 已取消 已完成 和所有的订单数据 并存入redux中

web3 React dapp项目通过事件从区块链中拿到 已取消 已完成 和所有的订单数据 并存入redux中

好 上文web3通过antd 在React dapp中构建订单组件基本结构我们算是把一个基本的订单组件展示做出来了 然后 我们继续 起一下环境先 ganache 终端运行 ganache -dMetaMask 登录一下 然后 打开项目 发布一下合约 truffle migrate --reset然后 运行一下 测试脚本 转入交易所 E…
阅读更多...
linux地址空间

linux地址空间

地址空间 内存空间示意图虚拟地址空间虚拟地址进程地址空间生命周期图解为什么要有地址空间呢&#xff1f; 小结 内存空间示意图 进程是在内存中运行的&#xff0c;为了便于管理&#xff0c;不同的数据会存储在不同的区域&#xff0c;因此内存就被分为几部分&#xff0c;如下图…
阅读更多...
在MacBook上实现免费的PDF文件编辑

在MacBook上实现免费的PDF文件编辑

之前我想对PDF文件进行简单处理&#xff08;比如删页面、添空白页、调整页面顺序&#xff09;&#xff0c;要么是开wps会员【花钱贵】&#xff0c;下载&#xff08;盗版&#xff09;Adobe Acrobat【macOS不好下载】&#xff0c;要么用福昕阅览器登陆学生账号&#xff08;学校买…
阅读更多...
逆向-文心一言开发者控制台调试

逆向-文心一言开发者控制台调试

一打开标准的无限debugger 往上一层可以发现是jsvmp&#xff0c;这样替换文件相对来说就不太好搞 根据测试如果卡在debugger就会跳转页面 但是放行debugger就可以正常使用 可以基本确定debugger前后存在计时程序 这个时候就可以考虑对apply做hook劫持无限debugger的函数&#…
阅读更多...
Eolink Apikit 版本更新：「数据字典」功能上线、支持 MongoDB 数据库操作、金融行业私有化协议、GitLab 生成 API 文档...

Eolink Apikit 版本更新：「数据字典」功能上线、支持 MongoDB 数据库操作、金融行业私有化协议、GitLab 生成 API 文档...

&#x1f389; 新增 搭建自定义接口协议架构&#xff0c;支持快速适配金融行业各类型私有协议的导入、编辑和展示。 数据字典功能上线&#xff0c;支持以数据字典的形式管理参数枚举值&#xff1b; 数据库连接支持 MongoDB 数据库操作&#xff1b; 基于 Apikit 类型导入 API…
阅读更多...
Mac下flutter工程配置Gitlab cicd打包（暂时仅限android侧）

Mac下flutter工程配置Gitlab cicd打包（暂时仅限android侧）

写的太粗糙&#xff0c;可能不太适合完全不懂的同学&#xff0c;但是实在没时间&#xff0c;而且也不太会写&#xff0c;权当做一个记录吧&#xff0c;对了还没有搞docker这些&#xff0c;还在持续学习中 1.GitLab Runner&#xff08;打包机&#xff09; 注意:需要有对应的权…
阅读更多...
BIM、建筑机器人、隧道工程施工关键技术

BIM、建筑机器人、隧道工程施工关键技术

一、BIM简介 &#xff08;一&#xff09;BIM概念 BIM&#xff08;Building Information Modeling&#xff09;&#xff0c;建筑信息模型。该技术通过数字化手段&#xff0c;在计算机中建立虚拟建筑&#xff0c;该虚拟建筑提供从单一到完整、包含逻辑关系的建筑信息库。信息库…
阅读更多...
遇到不可复现的bug要怎么做？

遇到不可复现的bug要怎么做？

测试人员遇到不可复现的bug要怎么做&#xff1f; 这是一个很常见的问题&#xff0c;也是一个很棘手的问题。不可复现的bug可能会给测试人员带来很大的困扰和压力&#xff0c;因为它们可能会影响软件的质量和用户的体验&#xff0c;但又很难找到问题的根源和解决方法。因此&…
阅读更多...
软件测试/测试开发丨如何利用ChatGPT自动生成测试用例思维导图

软件测试/测试开发丨如何利用ChatGPT自动生成测试用例思维导图

点此获取更多相关资料 简介 思维导图是一种用图形方式表示思维和概念之间关系的工具&#xff1a; 有些公司会使用思维导图编写测试用例&#xff0c;这样做的优点是&#xff1a; 1.可视化和结构化。 2.易于理解&#xff0c;提高效率。 而 ChatGPT 是无法直接生成 xmind 格式…
阅读更多...
深度学习中的数据类型介绍：FP32, FP16, TF32, BF16, Int16, Int8 ...

深度学习中的数据类型介绍：FP32, FP16, TF32, BF16, Int16, Int8 ...

文章目录 0. 前言1. 数据的存储方式2. 不同数据类型介绍2.1 深度学习中常用的数据类型2.2 BF16 类型的优势2.3 不同数据类型的使用场景 0. 前言 相比于 CPU&#xff0c;GPU 在架构设计时将更多的晶体管用于数据处理&#xff0c;而不是数据缓存和流量控制&#xff0c;因此可以高…
阅读更多...
Ansible 自动化运维工具 --- playbook 剧本

Ansible 自动化运维工具 --- playbook 剧本

文章目录 1. Host inventory ---- 主机清单1.1 简介1.2 inventory文件1.3 Inventory 文件的构成1.3.1 主机与组1.3.2 变量 1.4 inventory 中的常用变量 2. Ansible-playbook剧本2.1 简介2.2 Playbook的结构组成2.3 编写playbook的基本格式与写法2.3.1 基本格式2.3.2 语句的横向…
阅读更多...
【Linux】服务器与磁盘补充知识，硬raid操作指南

【Linux】服务器与磁盘补充知识，硬raid操作指南

服务器硬件 cpu 主板 内存 硬盘 网卡 电源 raid卡 风扇 远程管理卡 1.硬盘尺寸： 目前生产环境中主流的两种类型硬盘 3.5寸 和2.5寸硬盘 2.5寸硬盘可以通过使用硬盘托架后适用于3.5寸硬盘的服务器 但是3.5寸没法转换成2.5寸 2.如何在服务器上制作raid 华为服务器为例子做…
阅读更多...
Python中通过socketserver库创建服务端

Python中通过socketserver库创建服务端

socketserver库是Python的标准库&#xff0c;提供了套接字服务端的框架&#xff0c;通过该框架可以简化服务端的创建流程。 1 socketserver库的导入 通过如图1显示的代码导入socketserver库。 图1 导入socketserver库 2 通过socketserver库创建TCP服务端 通过socketserver库…
阅读更多...
二维码智慧门牌管理系统升级解决方案：轻松实现辖区范围门址统计

二维码智慧门牌管理系统升级解决方案：轻松实现辖区范围门址统计

文章目录 前言一、系统功能与优势 前言 在这个数字化时代&#xff0c;传统的门牌管理系统已经无法满足现代管理的需求。为了满足辖区内门址的统计需求&#xff0c;我们引入了全新的二维码智慧门牌管理系统升级解决方案。这一升级将让您轻松实现辖区范围门址的统计&#xff0c;…
阅读更多...
20.7 OpenSSL 套接字SSL加密传输

20.7 OpenSSL 套接字SSL加密传输

OpenSSL 中的 SSL 加密是通过 SSL/TLS 协议来实现的。SSL/TLS 是一种安全通信协议&#xff0c;可以保障通信双方之间的通信安全性和数据完整性。在 SSL/TLS 协议中&#xff0c;加密算法是其中最核心的组成部分之一&#xff0c;SSL可以使用各类加密算法进行密钥协商&#xff0c;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023