当前位置: 首页 > 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…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...