当前位置: 首页 > news >正文

【初阶数据结构】——堆排序和TopK问题

 =========================================================================

个人主页

代码仓库

C语言专栏

初阶数据结构专栏

Linux专栏

 =========================================================================

接上篇二叉树和堆的引入

========================================================================= 

目录

前言

建堆

插入数据向上调整算法建堆

移动数据向上调整算法建堆

无序数组从H-1层向上移动的向下调整算法建堆

堆排序

TOP-K问题


前言

上篇文章详细讲解了堆,最后在执行完整代码后我们发现在删除堆中的数据时可以实现排序,当然这不是偶然,一切都是有迹可循的,今天就来讲解下用堆来实现排序,以及使用堆排序解决TopK问题。

建堆

插入数据向上调整算法建堆

上篇文章中我们就实现了这个步骤,在主函数中创建了个数组然后将数组中的每个数据使用插入函数和向上调整算法函数依次插入动态开辟的空间中,每插入一个数据作为孩子和父亲相比较,根据大小交换位置,最终实现大/小堆。

插入函数

void HPPush(HP* php, HPDatatype x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDatatype* tmp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*newcapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;HPadjustUp(php->a, php->size-1);
}

进入函数首先判断空间大小是否足够 ,不够的话使用realloc库函数开辟空间,开辟不成功直接退出,开辟成功的话赋值和修改size和容量。 

向上调整函数和交换函数 

void HPadjustUp(HPDatatype* a, int child)
{//找到父亲int parent = (child - 1) / 2;//根为0  当和根交换后child为0while (child > 0){//当child小时和父亲交换 建成小堆//当child大时和父亲交换 建成大堆if (a[parent] > a[child]){swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

 进入向上调整函数根据我们上篇内容提供父亲和孩子之间下标的关系,依次向上调整根据我们的需要和父亲孩子的大小关系,用交换函数实现大/小堆。

​
void swap(HPDatatype* x, HPDatatype* y)
{HPDatatype tmp = *x;*x = *y;*y = tmp;
}​

为防止局部变量出交换函数作用域被销毁,这里我们使用指针交换。

这种方式的缺点

1.需要动态开辟空间,造成空间浪费。

2.需要完整的堆实现的代码,比较麻烦不是很推荐。

我们可以使用下面的方法对上面的函数进行优化。


移动数据向上调整算法建堆

根据我们这个方法的名字就可以判断我们这个方法是不需要动态开辟额外的空间,只需要使用数组下标通过向上调整算法函数来实现。

实现代码

	for (int i = 1; i < n; i++){HPadjustUp(a, i);}

 这里我们将数组中的第一个数据作为一个堆通过下标的移动让后面的数字和前面的数字比较,也就相相当于前面的数字作为父亲后面的数字作为孩子,父亲和孩子使用向上调整函数进行调整实现堆。

像这样经过多次的移动就形成我们的堆。  


无序数组从H-1层向上移动的向下调整算法建堆

上篇文章我们介绍了向下移动的调整算法,但是这个算法有个前提就是除根外的左右子树都要是堆,但是我们这里给定一个无序数组先让这个数组模拟成堆,除根外左右子树有可能都不是堆,就无法实现向下调整算法,这样我们从倒数第一个非子叶结点开始向下调整也就是最后一个结点的父亲开始向下调整,我们直到数组在空间中是连续的,那我们从这个结点开始没向下调整依次,这个结点向前移动依次这样就将一个大堆分成各个小堆,完成向下调整了。

实现代码

for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}

像这样经过多次的向下调整,最终就可以实现堆。 


堆排序

在实现堆排序之前我们先思考下升序和降序需要建什么堆?

我们这里直接给出答案:

升序:建大堆

降序:建小堆

问什么会是这样呢?

在上篇文章中堆的删除中,我们已经隐含的告诉大家了,如果我们要删除堆中的数据时直接向前移动数据会造成不是原有的大堆或者小堆,因此我们将根结点的数据和最后一个数据交换,两个子树依然是堆然后进行向下调整,size向前移动。我们不做删除这一步是不是就是排序!

实现代码

int end = n - 1;while (end > 0){swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}

TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 前k个数建小堆for (int i = (k-2)/2; i >=0 ; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){// 替换你进堆minheap[0] = x;// 向下调整算法函数AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);fclose(fout);
}// fprintf  fscanfvoid CreateNDate()
{// 造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{//CreateNDate();PrintTopK("data.txt", 5);return 0;
}

文件操作知识忘了的话自己回顾下。

今天的内容到这里就结束了,感谢大家的观看!可以在评论区多多交流和探讨,指出我的错误!

下篇文章将讲解完全二叉树的实现!请大家敬请期待!!!

相关文章:

【初阶数据结构】——堆排序和TopK问题

个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏 接上篇二叉树和堆的引入 目录 前言 建堆 插入数据向上调整算法建堆 移动数据向上调整算法建堆 无序数组从H-1层向上移动的向下调整算法建堆 堆排序 TOP-K问题 前言 上篇文章详细讲解了堆&#xff0c;…...

LLM - 大模型速递 InternLM-20B 快速入门

目录 一.引言 二.模型简介 1.模型特性 2.模型评测 三.模型尝试 1.模型参数 2.generate 与 chat 3.模型微调 四.总结 一.引言 一早醒来国产开源大模型又添一员猛将&#xff0c;书生-浦语大模型 InternLM-20B 大模型发布并开源&#xff0c;这里字面翻译是实习生大模型&…...

探索AIGC人工智能(Midjourney篇)(四)

文章目录 Midjourney模特换装 Midjourney制作APP图标 Midjourney网页设计 Midjourney如何生成IP盲盒 Midjourney设计儿童节海报 Midjourney制作商用矢量插画 Midjourney设计徽章 Midjourney图片融合 Midjourney后缀参数 Midjourney模特换装 关键词生成模特照片 中国女性模特的…...

uni-app:跨页面传递数组

A页面&#xff1a; JSON.stringify() 是一个 JavaScript 内置的方法&#xff0c;用于将 JavaScript 对象或值转换为 JSON 字符串。 //查看详细信息 details(e){// console.log(e.currentTarget.dataset.id)var device JSON.stringify(e.currentTarget.dataset.id)uni.naviga…...

element 表格拖拽保存插件

这是以前看着一篇文章 1.下载包 npm install sortablejs --save 2.在页面中引入&#xff0c;或者全局引入 import Sortable from ‘sortablejs’ 3.在template中 <div id"second"><el-tableclass"threeTable":style"{height:tableData.len…...

通过内网穿透,在Windows 10系统下搭建个人《我的世界》服务器公网联机

文章目录 1. Java环境搭建2.安装我的世界Minecraft服务3. 启动我的世界服务4.局域网测试连接我的世界服务器5. 安装cpolar内网穿透6. 创建隧道映射内网端口7. 测试公网远程联机8. 配置固定TCP端口地址8.1 保留一个固定tcp地址8.2 配置固定tcp地址 9. 使用固定公网地址远程联机 …...

C++11异步任务轮子实现(header-only)

为什么写这个 C17异步任务需要future和promise配合使用&#xff0c;不是很喜欢那种语法。实现一个操作简洁的异步任务。 满足功能 异步任务超时控制get接口同步任务计时lambda回调任务重启 使用 #include "async_callback.h" #include <unistd.h> #includ…...

2023华为杯研究生数学建模竞赛选题建议+初步分析

如下为C君的2023华为杯研究生数学建模竞赛&#xff08;研赛&#xff09;选题建议初步分析 2023华为杯研究生数学建模竞赛&#xff08;研赛&#xff09;选题建议 提示&#xff1a;DS C君认为的难度&#xff1a;CE<D<F&#xff0c;开放度&#xff1a;CDE<F。 华为专项…...

多线程并发或线程安全问题如何解决

1、通过volatile关键字修饰变量&#xff0c;可以实现线程之间的可见性&#xff0c;避免变量脏读的出现&#xff0c;底层是通过限制jvm指令的重新排序实现的&#xff0c;适用于一个线程修改&#xff0c;多个线程读的场景。 2、通过synchronized锁&#xff08;任意对象&#xff0…...

深度学习——线性神经网络一

深度学习——线性神经网络一 文章目录 前言一、线性回归1.1. 线性回归的基本元素1.1.1. 线性模型1.1.2. 损失函数1.1.3. 解析解1.1.4. 随机梯度下降1.1.5. 用模型进行预测 1.2. 向量化加速1.3. 正态分布与平方损失1.4. 从线性回归到深度网络 二、线性回归的从零开始实现2.1. 生…...

利用大模型知识图谱技术,告别繁重文案,实现非结构化数据高效管理

我&#xff0c;作为一名产品经理&#xff0c;对文案工作可以说是又爱又恨&#xff0c;爱的是文档作为嘴替&#xff0c;可以事事展开揉碎讲清道明&#xff1b;恨的是只有一个脑子一双手&#xff0c;想一边澄清需求一边推广宣传一边发布版本一边申报认证实在是分身乏术&#xff0…...

Java抽象类和普通类区别、 数组跟List的区别

抽象类 Java中的抽象类是一种特殊的类&#xff0c;它不能被实例化&#xff0c;只能被继承。抽象类通常用于定义一些通用的属性和方法&#xff0c;但是这些方法的具体实现需要在子类中完成。抽象类中可以包含抽象方法和非抽象方法。 抽象方法是一种没有实现的方法&#xff0c;…...

Leetcode.2522 将字符串分割成值不超过 K 的子字符串

题目链接 Leetcode.2522 将字符串分割成值不超过 K 的子字符串 rating : 1605 题目描述 给你一个字符串 s s s &#xff0c;它每一位都是 1 1 1 到 9 9 9 之间的数字组成&#xff0c;同时给你一个整数 k k k 。 如果一个字符串 s s s 的分割满足以下条件&#xff0c;我们…...

成绩分析(蓝桥杯)

成绩分析 题目描述 小蓝给学生们组织了一场考试&#xff0c;卷面总分为 100 分&#xff0c;每个学生的得分都是一个 0 到 100 的整数。 请计算这次考试的最高分、最低分和平均分。 输入描述 输入的第一行包含一个整数 n (1≤n≤104 )&#xff0c;表示考试人数。 接下来 n 行…...

【多思路附源码持续更新】2023年华为杯(中国研究生数学建模)竞赛C题

赛题 若官网拥挤&#xff0c;数据集和赛题下载地址如下&#xff1a; https://download.csdn.net/download/weixin_47723732/88364777 历届优秀论文下载地址&#xff0c;可以做参考文章 https://download.csdn.net/download/weixin_47723732/88365222 论文万能模板下载地址 htt…...

基于STM32设计的校园一卡通(设计配套的手机APP)

一、功能介绍 【1】项目介绍 随着信息技术的不断发展,校园一卡通作为一种高效便捷的管理方式,已经得到了广泛的应用。而其核心部件——智能卡也被越来越多的使用者所熟知。 本文介绍的项目是基于STM32设计的校园一卡通消费系统,通过RC522模块实现对IC卡的读写操作,利用2…...

有了Spring为什么还需要SpringBoot呢

目录 一、Spring缺点分析 二、什么是Spring Boot 三、Spring Boot的核心功能 3.1 起步依赖 3.2 自动装配 一、Spring缺点分析 1. 配置文件和依赖太多了&#xff01;&#xff01;&#xff01; spring是一个非常优秀的轻量级框架&#xff0c;以IOC&#xff08;控制反转&…...

【记录】Python 之于 C/C++ 区别

记录本人在 Python 上经常写错的一些地方&#xff08;C/C 写多了&#xff0c;再写 Python 有点切换不过来&#xff09; 逻辑判断符号用 and、or、!可以直接 10 < num < 30 比较大小分支语句&#xff1a;if、elif、else使用 、-&#xff0c;Python 中不支持 、- - 这两个…...

【Vue-Element-Admin】dialog关闭回调事件

背景 点击导入按钮&#xff0c;调出导入弹窗&#xff0c;解析excel数据后&#xff0c;不点击【确认并导入】按钮&#xff0c;直接关闭弹窗&#xff0c;数据违背清理 实现 使用dialog的close回调函数&#xff0c;在el-dialog添加close&#xff0c;在methods中定义closeDialog…...

Ansible自动化:简化你的运维任务

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...