【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

 🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

​​

目录

堆排序

第一种

 ​编辑

第二种

 TOP-K问题

建堆的时间复杂度

向下调整建堆的时间复杂度:

 向上调整建堆的时间复杂度:

 补充


 

   前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了堆排序,top-k问题和时间复杂度的内容
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

 

堆排序

第一种

 

假如左右子树都是小堆,我们只需要进行向下调整建堆即可。

下方是建大堆: 

 

思路分析:这里的向上和向下调整都是建大堆的。如果我们想进行升序排序,我们就得先建大堆。因为小堆的同一层中,无法进行比较。 接着,交换根结点和最后一个结点,这时就已经将最大的数排在末尾了。然后再从根结点向下调整建大堆,这时第二大的数就排在了根结点,再swap进行交换。end--表示不再对已排好的数进行操作。如此循环,即可进行升序。

总结:如果是升序,就要建大堆。如果是降序,就要建小堆。 堆排序的本质是选择排序。

        建堆的时间复杂度:N*logN

        选数的时间复杂度:(N-1)*logN

第二种

当左右子树不一定都是小堆时,我们就要进行从下往上的向下调整建堆

方法:从倒数第一个非叶子开始(即最后一个节点的父亲)。9,2,8,5不用调,我们从1开始,1和9满足小堆。接着往前一位数到2,此时也满足小堆。继续往前到6,1和5比,1更小,所以1和6交换。接着来到4,交换后的1和2,1更小,4就和1交换

此方法的时间复杂度是O(N),并且此方式只需要一个向下调整,不需要多写一个向上调整函数。

 

建小堆时,我们就会得到降序的数据。 

 

 TOP-K问题

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

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

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

举例如下:

   

我们先生成一千万个随机数。

topk函数如下:

void PrintTopK(const char* file, int k)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
	//建一个k个数的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	//读取前k个,建小堆
	for (int i = 0; i < k;i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		AdjustUp(minheap, i);
	}

	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);
}

 我们先建立k个数的小堆,并将前k个数放进去。接着从第k+1开始的数开始与根结点比较,如果大于,就替换,然后进行向下调整,恢复成堆的形式。直到所有的数都比较完,我们就能找出前k个最大或最小的数了。

最后的运行结果如下:

  

建堆的时间复杂度

向下调整建堆的时间复杂度:

这里举例向下调整建堆的时间复杂度:

因为第h层是叶,就不需要向下移动了。具体计算过程如下图,因为是等差*等比,所以采用错位相减法进行计算。

因为最后的结果中的h是树的高度,不方便看出时间复杂度,替换成N(节点的个数)

 

最终,时间复杂度是O(N)。

 向上调整建堆的时间复杂度:

 

 

上方是求向上调整建堆时间复杂度的计算过程,原理与向下调整的一样。

最终的时间复杂度是:O(N*logN)

 补充

上方的过程的时间复杂度是O(N*logN),他跟上方的向上调整建堆相似,都是多*多,少*少的关系。因为最后一层有2^(h-1)个节点,每次交换后,最坏情况要向下调整(h-1)层,即多*多。第1层有一个节点,向下调整0层,即少*少。

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

npm install 无反应 npm run serve 无反应

说明情况&#xff1a;其实最开始我就是发现我跟着黑马的苍穹外卖的前端day2的环境搭建做的时候&#xff0c;到这一步出现了问题&#xff0c;无论我怎么 npm install 和 npm run serve 都没有像黑马一样有很多东西进行加载&#xff0c;因此我换了一种方法 1.在这个文件夹下cmd …

助力工业焊缝质量检测,YOLOv3开发构建工业焊接场景下钢材管道焊缝质量检测识别分析系统

焊接是一个不陌生但是对于开发来说相对小众的场景&#xff0c;在我们前面的博文开发实践中也有一些相关的实践&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《轻量级模型YOLOv5-Lite基于自己的数据集【焊接质量检测】从零构建模型超详细教程》 《基于DeepLabV3Pl…

计算机组成原理-程序中断方式完整流程

文章目录 程序中断方式完整流程例题小结 程序中断方式完整流程 首先CPU通过执行IO指令来启动外部设备&#xff0c;此时外部设备可以开始做准备工作了&#xff08;准备CPU想要的数据或者信息&#xff09;&#xff0c;在外部设备准备过程中&#xff0c;CPU可以继续执行原程序的内…

CES 2024,从枕头到汽车,一切皆可AI

文 / 胡泳 北京大学新闻与传播学院教授 世界上最大的消费类电子展CES是令人难以置信的创新的展示舞台。 我在拉斯维加斯泡了四五天&#xff0c;跟踪了展出的大部分小工具、应用程序和概念产品。这些产品既有趣又实用&#xff0c;它们要么以全新的方式利用技术解决了某个特定的问…

AI对决:ChatGPT与文心一言的比较

. 个人主页&#xff1a;晓风飞 专栏&#xff1a;数据结构|Linux|C语言 路漫漫其修远兮&#xff0c;吾将上下而求索 文章目录 引言ChatGPT与文心一言的比较Chatgpt的看法文心一言的看法Copilot的观点chatgpt4.0的回答 模型的自我评价自我评价 ChatGPT的优势在这里插入图片描述 文…

JS-var 、let 、 const使用介绍

变量声明介绍 在我们日常开发用&#xff0c;变量声明有三个 var、 let 和 const&#xff0c;我们应该用那个呢&#xff1f; 首先var 先排除&#xff0c;老派写法&#xff0c;问题很多&#xff0c;可以淘汰掉…let or const ?建议&#xff1a; const 优先&#xff0c;尽量使…

CSS 水浪按钮

<template><view class="content"><button class="button"><view class="liquid"></view><view class="btn-txt">水浪按钮</view></button></view></template><scrip…

QT上位机开发(MFC vs QT)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 在qt之前&#xff0c;上位机开发的主要方法就是mfc。后来出现了c#语言之后&#xff0c;上位机的开发就有一部分人转成了c#。这些开发都是在windows…

Vue + JS + tauri 开发一个简单的PC端桌面应用程序

Vue JS tauri 开发一个简单的PC端桌面应用程序 文章目录 Vue JS tauri 开发一个简单的PC端桌面应用程序1. 环境准备1.1 安装 Microsoft Visual Studio C 生成工具[^2]1.2 安装 Rust[^3] 2. 使用 vite 打包工具创建一个 vue 应用2.1 使用Vite创建前端Vue项目2.2 更改Vite打包…

Android Traceview 定位卡顿问题

Traceview 是一个 Android 性能分析工具&#xff0c;用于时间性能分析&#xff0c;主要帮助开发者了解应用程序中各个方法的执行时间和调用关系。通过图形化界面查看应用程序的代码执行细节&#xff0c;包括每个方法的调用次数、方法调用的时间消耗、方法调用堆栈等信息。我们可…

基于Python实现身份证信息识别

目录 前言身份证信息识别的背景与意义自动识别身份证的需求实现环境与工具准备Python编程语言OpenCV图像处理库Tesseract OCR引擎身份证信息识别算法原理图像预处理步骤(图像裁剪、灰度化 、二值化、去噪)信息提取与解析Python代码实现通过OCR提取身份证号码代码解析身份证信息…

uniapp 如何使用echarts 以及解决tooltip自定义不生效;dataZoom报错问题

使用的是echarts-for-wx插件&#xff1b; 正常写法案例&#xff1a;给tooltip数值加个% <template><view><uni-ec-canvas class"uni-ec-canvas"id"uni-ec-canvas"ref"canvas"canvas-id"uni-ec-canvas":ec"ec&quo…

某银行主机安全运营体系建设实践

随着商业银行业务的发展&#xff0c;主机规模持续增长&#xff0c;给安全团队运营工作带来极大挑战&#xff0c;传统的运营手段已经无法适应业务规模的快速发展&#xff0c;主要体现在主机资产数量多、类型复杂&#xff0c;安全团队难以对全量资产进行及时有效的梳理、管理&…

微软推出新的 Copilot Pro 计划

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

20240116-【UNITY 学习】增加滑动功能

替换脚本PlayerMovement_02.cs using System.Collections; using System.Collections.Generic; using UnityEngine;public class PlayerMovement_03 : MonoBehaviour {private float moveSpeed; // 玩家移动速度public float walkSpeed 7; // 行走速度public float sprintSpee…

第二讲_HarmonyOS应用创建和运行

HarmonyOS应用创建和运行 1. 创建一个HarmonyOS应用2. 运行新项目2.1 创建本地模拟器2.2 启动本地模拟器2.3 在本地模拟器运行项目 1. 创建一个HarmonyOS应用 打开DevEco Studio&#xff0c;在欢迎页单击Create Project&#xff0c;创建一个新工程。 选择创建Application应用。…

Vue 富文本实现内容项目倒序

应用场景&#xff1a; 比如写计划和待办事项&#xff0c;内容少还好&#xff0c;内容多了最新的内容就放在下面了&#xff0c;每次打开要滚动到最后才能看到&#xff0c;这时可以使用倒序把最新的排在最前面。 倒序前&#xff1a; 倒序后&#xff1a; 倒序代码&#xff1a; …

力扣hot100 二叉树中的最大路径和 递归

Problem: 124. 二叉树中的最大路径和 文章目录 解题方法复杂度&#x1f496; Code 解题方法 &#x1f468;‍&#x1f3eb; 参考思路 复杂度 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) &#x1f496; Code /*** Definition for a binary tree no…

Vue-16、Vue列表渲染(v-for的使用)

1、vue遍历数组 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>列表渲染</title><script type"text/javascript" src"https://cdn.jsdelivr.net/npm/vue2/dist/vue.js"…

手写OpenFeign(简易版)

Remoting组件实现 1. 前言2. 原理说明3. 远程调用组件实现---自定义注解3.1 添加Spring依赖3.2 编写EnableRemoting注解3.3 编写RemoteClient注解3.4 编写GetMapping注解 4. 远程调用组件实现---生成代理类4.1 编写自定义BeanDefinition注册器4.2 编写自定义包扫描器4.3 编写Fa…