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

【数据结构】二叉树--堆排序

目录

一 降序(建小堆)

二 升序 (建大堆)

​三 优化(以升序为例)

四 TOP-K问题


一 降序(建小堆)

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = 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 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)
{int end = n - 1;int i = 0;//建堆for (i = 1; i < n; i++){AdjustUp(a, i);}while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}int main()
{int a[] = { 2, 3, 5, 7, 4, 6, 8 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}

二 升序 (建大堆)

//升序 建大堆
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 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)
{int end = n - 1;int i = 0;//建堆for (i = 1; i < n; i++){AdjustUp(a, i);}while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}int main()
{int a[] = { 2, 3, 5, 7, 4, 6, 8 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}

三 优化(以升序为例)

可以用向下建堆的方法

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)
//{
//	int end = n - 1;
//	int i = 0;
//	//建堆
//	for (i = 0; i < n; i++)
//	{
//		AdjustUp(a, i);
//	}
//
//	while (end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdjustDown(a, end, 0);
//		end--;
//	}
//}void HeapSort(int* a, int n)
{int end = n - 1;int i = 0;//建大堆for (i = (n-1-1) / 2; i >= 0; i--){AdjustDown(a, n, i);}while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] = { 2, 3, 5, 7, 4, 6, 8, 65, 100, 70, 32, 50, 60};HeapSort(a, sizeof(a) / sizeof(int));return 0;
}

 

这样建堆的方式对时间复杂度有什么优化吗?

 

四 TOP-K问题

TOP - K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top - K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:1. 用数据集合中前K个元素来建堆

    前k个最大的元素,则建小堆

    前k个最小的元素,则建大堆

2. 用剩余的N - K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>typedef int HPDataType;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(HPDataType* 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 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");fclose(fout);}void CreateDate()
{//造数据int n = 100000;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) % n;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{CreateDate();PrintTopK("data.txt", 5);return 0;
}

 

本节对前面的二叉树基础很高, 没有理解的, 可以翻看我之前对二叉树顺序结构及其实现的章节.

继续加油! 

相关文章:

【数据结构】二叉树--堆排序

目录 一 降序(建小堆) 二 升序 (建大堆) ​三 优化(以升序为例) 四 TOP-K问题 一 降序(建小堆) void Swap(int* x, int* y) {int tmp *x;*x *y;*y tmp; }//降序 建小堆 void AdjustUp(int* a, int child) {int parent (child - 1) / 2;while (child > 0){if (a[chil…...

项目log日志mysql记录,熟悉python的orm框架

直接在项目里面创建一个class&#xff0c;这个类对应着mysql里面的表 我们运行项目&#xff0c;可以自动建立表 在.env中找到mysql的配置信息&#xff0c;这个是在NB服务器上运行的mysql&#xff0c;localhost需要变成NB服务器的ipv4地址 使用Mysql工具连接查看&#xff0c;连…...

【数据结构-字符串 四】【字符串识别】字符串转为整数、比较版本号

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【字符串转换】&#xff0c;使用【字符串】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&…...

React 组件传 children 的各种方案

自定义组件的时候往往需要传 children&#xff0c;由于写法比较多样&#xff0c;我就总结了一下。 方案列表 1. 类组件1.1 类组件&#xff0c;不使用解构1.2 类组件&#xff0c;使用解构 2. 函数组件2.1 函数组件&#xff0c;不使用解构2.2 函数组件&#xff0c;外部解构2.3 函…...

如何在一个传统的html中,引入vueJs并使用vue复制组件?

如何在一个传统的html中&#xff0c;引入vueJs并使用vue复制组件&#xff1f; 1.1 引言1.2 背景1.3 解决方案1.3.1 解决方案一&#xff1a;直接使用clipboard(不推荐仅供参考学习)1.3.2 解决方案二&#xff1a;封装指令js库后使用 (推荐) 1.1 引言 这篇博文主要分享如何在一个…...

【轻松玩转MacOS】故障排除篇

引言 在使用 MacOS 时&#xff0c;遇到故障是在所难免的。不要担心&#xff0c;这篇文章将为您提供一些常见的故障排除步骤&#xff0c;并介绍如何联系苹果的支持团队寻求帮助。让我们一起来看看吧&#xff01; 一、常见的故障排除步骤 1.1 网络连接问题 如果你发现你的Mac…...

Linux基本指令(1)

Linux基本指令&#xff08;1&#xff09; 1.ls指令1.1ls的用法 2. pwd指令3.cd指令3.1 cd3.2补充内容3.3 cd - 指令3.4 cd ~ 指令 4. touch指令4.1stat指令 5.mkdir 指令6.rmdir/rm指令6.1补充内容 7.man指令8.nano 指令9.cat指令10 cp指令11 mv指令12 echo指令12.1 > 输出重…...

计算机毕业设计选题推荐-springboot 网上手机销售系统

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…...

2、vscode c++ 项目配置调试及运行

文章目录 1、项目布局2、多项目管理2.1 先是一个总的CMakeLists.txt2.2 每个项目2.3 多版本OPENCV 3、调试和运行 接上一篇文章&#xff0c;vscode和cmake的c环境配置好以后&#xff0c;我们要写项目&#xff0c;再写对应的CMakeLists.txt 1、项目布局 . ├── bin ├── bu…...

二叉搜索树的最近公共祖先

二叉搜索树的最近公共祖先-力扣 235 题 求二叉搜索树最近公共祖先&#xff08;祖先也包括自己&#xff09; 前提&#xff1a; 1.节点值唯一 2.p和q都存在 要点&#xff1a;若 p&#xff0c;q 在 ancestor 的两侧&#xff0c;则 ancestor 就是它们的最近公共祖先 解题思路&…...

LuatOS-SOC接口文档(air780E)-- i2c - I2C操作

常量 常量 类型 解释 i2c.FAST number 高速 i2c.SLOW number 低速 i2c.exist(id) i2c编号是否存在 参数 传入值类型 解释 int 设备id, 例如i2c1的id为1, i2c2的id为2 返回值 返回值类型 解释 bool 存在就返回true,否则返回false 例子 -- 检查i2c1是否存…...

帝国cms改目录后打不开,帝国cms改目录生成后还是404

帝国CMS更改了网站域名或者栏目目录地址信息打不开的解决方法&#xff0c;一起来看看吧&#xff1a; 很多的小伙伴们&#xff0c;改了后台的系统设置里面的网站地址或者栏目目录地址&#xff0c;信息页就打不开的解决方法如下&#xff1a; 后台>系统>数据更新>更新信…...

计算机毕业设计选什么题目好?springboot智慧养老中心管理系统

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…...

创建一个基本的win32窗口

1.建立一个窗口的基本步骤 &#xff08;1&#xff09;向系统注册一个窗体类 &#xff08;2&#xff09;根据窗体类创建窗口 &#xff08;3&#xff09;进入消息循环 2.程序结构 (1)主函数的输入参数 int WINAPI WinMain( HISTANCE hInstance,//当前窗口的句柄 HINSTANCE hPr…...

如何在 Spring Boot 中使用 WebSocket

在Spring Boot中使用WebSocket构建实时应用 WebSocket是一种用于实现双向通信的网络协议&#xff0c;它非常适合构建实时应用程序&#xff0c;如在线聊天、实时通知和多人协作工具。Spring Boot提供了对WebSocket的支持&#xff0c;使得在应用程序中集成WebSocket变得非常容易…...

ubuntu2023装完显卡驱动和CUDA CUDNN开机只有下划线闪烁

解决方法 网上很多方案&#xff0c;如Ubuntu开机后卡死只有左上角有一个下划线不停闪烁_ubuntu开机左上角横杠一直闪-CSDN博客&#xff0c;原因是显卡驱动和系统内核不兼容&#xff0c;解决方案是CtrlAltF2打开tty模式进行问题检查 但是我CtrlAltF2完全没反应。 于是&#xf…...

MySQL三种安装方法(yum安装、编译安装、二进制安装)

mysql安装 一、yum安装方式二、编译安装方式三、二进制安装方式 切记&#xff1a;一定要关闭防火墙和selinux&#xff01;&#xff01;&#xff01; 服务器配置&#xff1a;2C4G即可&#xff0c;一台 一、yum安装方式 mysql的官方网站&#xff1a;www.mysql.com 中文官网&…...

《视觉 SLAM 十四讲》第 7 讲 视觉里程计1 【如何根据图像 估计 相机运动】【特征点法】

github源码链接V2 文章目录 第 7 讲 视觉里程计17.1 特征点法7.1.1 特征点7.1.2 ORB 特征FAST 关键点 ⟹ \Longrightarrow ⟹ Oriented FASTBRIEF 描述子 7.1.3 特征匹配 7.2 实践 【Code】本讲 CMakeLists.txt 7.2.1 使用 OpenCV 进行 ORB 的特征匹配 【Code】7.2.2 手写 O…...

9. 一个SpringBoot项目运行

新手如何运行一个SpringBoot项目 1.SpringBoot项目运行 新创建的SpringBoot项目如何运行 2.启动lombok注解 点击该按钮&#xff0c;启动lombok注解支持 3.展示说明...

如何实现chatGPT批量问答,不用token

一、背景 因为需要批量提取一本教材里的概念做成知识图谱&#xff0c;想用chatGPT做概念提取。 调用api&#xff1f;别想了… 免费帐户的api慢得一批于是想用模仿人类交互的方法来调用&#xff0c;本来想用pyautogui的&#xff0c;但是主要是与浏览器交互&#xff0c;还是用s…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...