【数据结构】堆的应用(堆排序的实现 + (向上/向下)建堆时间复杂度证明 + TopK问题(笔记总结))

news/2024/4/24 16:43:43/

在这里插入图片描述

👦个人主页:@Weraphael
✍🏻作者简介:目前学习C++和算法
✈️专栏:数据结构
🐋 希望大家多多支持,咱一起进步!😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨


【本章内容】

在这里插入图片描述

标题

  • 一、堆排序
    • 1.1 堆排序的思想
    • 1.2 堆排序排升序思路
    • 1.3 建堆
      • 1.31 向上调整建堆
      • 1.32 向上建堆时间复杂度证明
      • 1.33 向下调整建堆
      • 1.34 向下建堆时间复杂度证明
    • 1.4 调整
      • 1.41 调整代码实现
      • 1.42 调整复杂度证明
    • 1.5 完整代码 + 整体时间复杂度
  • 二、TOP-K问题
    • 2.1 什么是TOP-K问题
    • 2.2 TOP-K问题的基本思路
    • 2.3 取最大的前TOP-K
    • 2.4 代码实现

一、堆排序

1.1 堆排序的思想

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序
    建堆和堆删除中都运用到了向下调整。但是,建堆也可以用向上调整,只是向上调整的时间复杂度高于向下调整(后面有证明过程)

1.2 堆排序排升序思路

在《堆排序的思想》中,总结了升序要建大堆,为什么要建大堆呢?首先大堆的特点是:父亲结点总大于或等于孩子结点。因此建完大堆后,根节点就是最大的,而又要保持升序。所以,我们可以将根结点和尾结点进行交换,这样最大的元素就在最后一个了,然后再以根结点向下调整(注意调整的时候不要再动尾结点了),这样次大的元素又在根结点上了,重复以上操作,即可以用堆排序排升序。

1.3 建堆

1.31 向上调整建堆

  • 向上调整建堆就是从第二层模拟插入的过程
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = 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 HeapSort(int* a, int n)
{//1. 建堆//法一:向上调整建堆(大堆)for (int i = 1; i < n; i++){Adjust(a, i);}
}int main()
{int a[] = { 4,7,10,8,1,5,2,3 };//数组元素个数Asizeint Asize = sizeof(a) / sizeof(a[0]); //堆排序HeapSort(a, Asize);//打印for (int i = 0; i < Asize; i++)printf("%d ", a[i]);printf("\n");return 0;
}

此篇博客详细讲解了建大堆的过程 -->【传送门】

1.32 向上建堆时间复杂度证明

由于一般时间复杂度通常都是看最坏的,因此以满二叉树为例,因为它的结点个数最多。

在这里插入图片描述

向上建堆是从第二层开始模拟插入过程的。现假设二叉树的高度为h,T(N)表示建堆的总次数。那如何列出总次数的式子呢?我们可以拿(每一层结点个数如上图)每一层结点的个数 × 最坏调整次数。例如,从第二层开始向上建堆可以列出 2 1 × 1 2^1×1 21×1,第三层可以列出 2 2 × 2 2^2 × 2 22×2。后面因此类推。所以可以列出以下T(N)的表达式:
T ( N ) = 2 1 × 1 + 2 2 × 2 + 2 3 × 3 + . . . + 2 ( h − 2 ) × ( h − 2 ) + 2 ( h − 1 ) × ( h − 1 ) T(N) = 2^1×1 + 2^2×2 + 2^3×3 + ... + 2^(h-2)×(h-2) + 2^(h-1)×(h-1) T(N)=21×1+22×2+23×3+...+2(h2)×(h2)+2(h1)×(h1)
那该如何化简呢?这就要运用到高中的数学知识 — 错位相减法
在这里插入图片描述
再通过以下结论:
设满二叉树高度为h,总结点个数为N

  • 满二叉树的总结点个数 : N = 2 h − 1 N = 2^h - 1 N=2h1
  • 再根据数学知识化简以上等式: h = l o g N h = logN h=logN (以2为底)

在这里插入图片描述
带入结论得出:向上建堆的时间复杂度为:NlogN

1.33 向下调整建堆

#include <stdio.h>
//堆排序void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n, int parent)
{//假设左孩子一开始最大int child = parent * 2 + 1;//当child走到叶子节点循环结束,也就是说它不能超过数组的大小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)
{//1. 建堆//法二:向下调整建堆(大堆)for (int i = (n - 1 - 1) / 2; i >= 0; i--){Adjustdown(a, n, i);}
// i - 开始向下调整的根的下标
// n - 需要调整的元素个数
}

这里需要注意的是,这里的向下调整并不是从根结点开始的,而是从倒数第一个非叶子结点开始的。为什么呢?因为一开始数组内的元素都是随机的,而向下调整必须要满足左右子树都要有堆的性质。画个图可能会更加清晰点:
在这里插入图片描述
然后再来解释向下调整循环的细节,前头说过了,要从倒数第一个非叶子结点开始向下调整,对于上图来说,非叶结点的第一个结点也就是15,那么问题来了,如何找到15呢,在堆的章节已经说过了父亲结点和孩子结点的下标关系

  1. 如何找到父亲结点:parent = (child - 1)/ 2
  2. 如何找到左孩子结点 :leftchild = parent * 2 + 1
  3. 如何找到右孩子结点:rightchild = parent * 2 + 2(右孩子比左孩子的下标多1)

所以可以通过500的下标找到15,因此循环里的(n - 1 - 1) / 2n - 1代表的是最后一个元素的下标,再-1 /2即找到倒数第一个非叶子结点

1.34 向下建堆时间复杂度证明

和向上建堆的时间复杂度一样,以满二叉树为例

在这里插入图片描述

在向下调整过程中,由于是从倒数第二层结点开始向下调整的,倒数第二层结点总个数不难算出是 2(h-2)。现假设二叉树的高度为h,T(N)表示建堆的总次数。通过每一层结点的个数 × 最坏调整次数列出T(n)表达式如下:
T ( N ) = 2 ( h − 2 ) × 1 + 2 ( h − 3 ) × 2 + . . . + 2 1 × ( h − 2 ) + 2 0 × ( h − 1 ) T(N) = 2^(h-2)×1 + 2^(h-3)×2 + ... + 2^1×(h-2) + 2^0×(h-1) T(N)=2(h2)×1+2(h3)×2+...+21×(h2)+20×(h1)
然后通过错位相减法,过程如下:
在这里插入图片描述
再通过以下结论:
设满二叉树高度为h,总结点个数为N

  • 满二叉树的总结点个数 : N = 2 h − 1 N = 2^h - 1 N=2h1
  • 再根据数学知识化简以上等式: h = l o g N h = logN h=logN (以2为底)

在这里插入图片描述
带入结论得出:向下建堆的时间复杂度为:O(N)

总结:
向上建堆的时间复杂度为:O(NlogN),向下建堆的时间复杂度为:O(N)。因此,建堆时一般都使用向上建堆。

1.4 调整

我们已经完成了建堆,接下来根据《堆排序排升序思路》。将根结点和尾结点进行交换,然后再以根结点向下调整(注意调整的时候不要再动尾结点了),这样次大的元素又在根结点上了,重复以上操作,即可以用堆排序排升序。

1.41 调整代码实现

#include <stdio.h>
//堆排序void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n, int parent)
{//假设左孩子一开始最大int child = parent * 2 + 1;//当child走到叶子节点循环结束,也就是说它不能超过数组的大小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)
{//1. 建堆//法二:向下调整建堆(大堆)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//2. 调整int end = n - 1;//最后一个元素while (end > 0){//首尾交换Swap(&a[0], &a[end]);//向下调整AdjustDown(a, end, 0);end--;}//end是最后一个元素的下标//同时也是前面数据的个数
}

💀注意
交换完头尾两个元素后,向下调整的区间不要包括最后一个元素,因为最后一个元素已经是当前所有元素中最大的了

1.42 调整复杂度证明

可以这么想,因为满二叉树最后一层的结点个数占总结点个数的一半,因此可以只看最后一层
T ( N ) = 2 ( h − 1 ) × ( h − 1 ) = N l o g N T(N) = 2^(h-1) × (h-1) = NlogN T(N)=2(h1)×(h1)=NlogN

1.5 完整代码 + 整体时间复杂度

//堆排序
#include <stdio.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n, int parent)
{//假设左孩子一开始最大int child = parent * 2 + 1;//当child走到叶子节点循环结束,也就是说它不能超过数组的大小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)
{//1. 建堆//法二:向下调整建堆(大堆)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//2. 调整int end = n - 1;//最后一个元素while (end > 0){//首尾交换Swap(&a[0], &a[end]);//向下调整AdjustDown(a, end, 0);end--;}
}int main()
{int a[] = { 4,7,10,8,1,5,2,3 };//数组元素个数Asizeint Asize = sizeof(a) / sizeof(a[0]); //堆排序HeapSort(a, Asize);//打印for (int i = 0; i < Asize; i++)printf("%d ", a[i]);printf("\n");return 0;
}

【结果展示】

在这里插入图片描述

.🎈总结
向上建堆的时间复杂度是O(N),调整的时间复杂度是O(NlogN)。因此,堆排序的时间复杂度为O(Nlog(N)

二、TOP-K问题

2.1 什么是TOP-K问题

  • TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
  • TOP-K在生活中的应用:在班级取成绩前10名、游戏中给段位高的前100的玩家排名等。

2.2 TOP-K问题的基本思路

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

  1. 用数据集合中前K个元素来建堆
  • 取前k个最大的元素,则建小堆
  • 取前k个最小的元素,则建大堆
  1. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

2.3 取最大的前TOP-K

假设我们要取最大的前k个(取最小的前k个也是如此),就要建小堆,然后随机放入K个数据。为什么呢?因为小堆的特点是根结点是整个数据中最小的,然后剩余的N - K个元素依次与堆顶元素来比较,如果大于堆顶元素则交换,然后再进行向下调整。最后,重复以上操作,堆中小的数据都已经被替换了,剩下的就是最大的前K

2.4 代码实现

  • 建小堆
#include <stdio.h>
#include <stdlib.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n, int parent)
{//假设左孩子一开始最大int child = parent * 2 + 1;//当child走到叶子节点循环结束,也就是说它不能超过数组的大小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 GetTopK(int* a, int n, int k)
{//1. 建堆int* SmallHeap = (int*)malloc(sizeof(int) * k);if (SmallHeap == NULL)return;//2. 随机放入k个数据for (int i = 0; i < k; i++){SmallHeap[i] = a[i];}//3. 建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(SmallHeap, k, i);}
}
  • 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
//4. 将剩下的n - k个元素依次和堆顶元素比较for (int i = k; i < n; i++){//如果n-k个元素中有大于堆顶则交换if (a[i] > SmallHeap[0]){SmallHeap[0] = a[i];//交换完后再调整堆AdjustDown(SmallHeap, k, 0);}}//5.打印for (int i = 0; i < k; i++){printf("%d ", SmallHeap[i]);}printf("\n");

【完整代码】

// TopK问题:以找出N个数里面最大为例#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void Swap(int* a1, int* a2)
{int tmp = *a1;*a1 = *a2;*a2 = tmp;
}//小堆:父亲比孩子小
void AdjustDown(int* a, int n, int parent)
{//child一开始最小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(int* a, int n, int k)
{//1.建堆int* SmallHeap = (int*)malloc(sizeof(int) * k);assert(SmallHeap);//2. 随机向堆丢入k个数据for (int i = 0; i < k; i++){SmallHeap[i] = a[i];}//3.建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(SmallHeap, k, i);}//4. 将剩下的n - k个元素依次和堆顶元素比较for (int i = k; i < n; i++){//如果n-k个元素中有大于堆顶则交换if (a[i] > SmallHeap[0]){SmallHeap[0] = a[i];//交换完后再调整堆AdjustDown(SmallHeap, k, 0);}}//5.打印for (int i = 0; i < k; i++){printf("%d ", SmallHeap[i]);}printf("\n");
}int main()
{int a[] = { 20, 100, 4, 2, 87, 9, 8, 5, 46, 26 };int k = 3;int n = sizeof(a) / sizeof(a[0]);PrintTopK(a, n, k);return 0;
}

http://www.ppmy.cn/news/47662.html

相关文章

Flink Table API 和 Flink-SQL使用详解

Flink Table API 和 Flink-SQL使用详解 1.Table API & Flink SQL-核心概念 ​ Apache Flink 有两种关系型 API 来做流批统一处理&#xff1a; Table API Table API 是用于 Scala 和 Java 语言的查询API&#xff0c;它可以用一种非常直观的方式来组合使用选取、过滤、join…

RK3568平台开发系列讲解(调试篇)IS_ERR函数的使用

🚀返回专栏总目录 文章目录 一、IS_ERR函数用法二、IS_ERR函数三、内核错误码沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将介绍 IS_ERR 函数的使用。 一、IS_ERR函数用法 先看下用法: 二、IS_ERR函数 对于任何一个指针来说,必然存在三种情况: 一种是合…

电源常识-PCB材质防火等级焊锡工艺

1、目前主流的PCB材质分类主要有以下几种,如图1&#xff0c;图2&#xff0c;图3。FR-4材质比CEM-1好&#xff0c;CEM-1比FR-1好。 按结构分为单面板&#xff0c;双面板&#xff0c;多层板。单面板就是单面铺铜走线&#xff0c;双面板就是上下两面都可以铺铜走线&#xff0c;多层…

Guns社区医疗项目

又是一年毕业季&#xff0c;计算机专业大四的同学们要接受毕业设计的考验啦。又有多少同学为了毕业设计而愁眉苦脸&#xff0c;心力憔悴。考虑到这些&#xff0c;这里为同学们分享一个适合你们毕业设计的作品以及详细介绍&#xff0c;让正在焦头烂额的同学们有所启发&#xff0…

asp.net+C#房地产销售系统文献综述和开题报告+Lw

本系统使用了B/S模式&#xff0c;使用ASP.NET语言和SQL Server来设计开发的。首先把所有人分为了用户和管理员2个部分&#xff0c;一般的用户可以对系统的前台进行访问&#xff0c;对一般的信息进行查看&#xff0c;而注册用户就可以通过登录来完成对房屋信息的查看和对房屋的…

开发插件JFormDesigner(可视化GUI编程)的使用与注册-简单几步即可完成

开发插件JFormDesigner&#xff08;可视化GUI编程&#xff09;的使用与注册 获取链接&#xff1a;1.JFormDesigner获取2.记录插件下载路径3.使用zcj注册4.生成license5.打开idea进行注册 获取链接&#xff1a; https://pan.baidu.com/s/1N9ua2p3BpiMIARCEewRxIw?pwd4e9a 提取…

浅说情绪控制被杏仁体劫持

2023年4月16号&#xff0c;没想到被杏仁体劫持那么严重&#xff0c;触发手抖和口干的症状&#xff0c;这个还真是自己完全没有意识到的【这就是焦虑固化的记忆会持续化】。 【修行】人生要修炼两条线&#xff1a;一条明线是做的事情&#xff0c;那是自己要做的具体事情。 一条…

天梯赛 L2-034 口罩发放

原题链接&#xff1a; PTA | 程序设计类实验辅助教学平台 题目描述&#xff1a; 为了抗击来势汹汹的 COVID19 新型冠状病毒&#xff0c;全国各地均启动了各项措施控制疫情发展&#xff0c;其中一个重要的环节是口罩的发放。 某市出于给市民发放口罩的需要&#xff0c;推出了…

python-day6(补充三:实例变量和函数)

实例变量和函数 实例函数的定义认识__init__函数定义实例变量实例函数中访问实例变量外部访问实例变量与函数 实例函数的定义 定义实例函数 class Student:def say_hello(self, msg):print(f"hello{msg}")实例函数属于对象 class Student:def say_hello(self, m…

JMM之volatile关键字详解

1、概要 在JMM规范下有三大特性分别是&#xff1a;可见性、原子性、有序性。而被volatile关键字修饰的共享变量拥有三大特性的两大特性分别是&#xff1a;可见性和有序性。 为什么被volatile修饰的变量就可以保证变量的可见性和有序性呢&#xff1f;为啥不能保证原子性&#…

使用 PyTorch Geometric 和 GCTConv实现异构图、二部图上的节点分类或者链路预测

解决问题描述 使用 PyTorch Geometric 和 Heterogeneous Graph Transformer 实现异构图上的节点分类 在二部图上应用GTN算法(使用torch_geometric的库HGTConv)&#xff1b; 步骤解释 导入所需的 PyTorch 和 PyTorch Geometric 库。 定义 x1 和 x2 两种不同类型节点的特征&am…

如何在 TensorFlow 中使用 GPU 加速深度学习计算?

一、前言 TensorFlow 是由 Google 开源的深度学习框架,它具有易用、高效、灵活等特点,被广泛应用于学术界和工业界中。而 GPU 是一种高性能的计算设备,可以加速深度学习的计算过程。本文将介绍如何在 TensorFlow 中使用 GPU 加速深度学习计算。 二、安装 TensorFlow 安装…

Python语言中的注释方法应用

Python语言中的注释方法 在Python编程中&#xff0c;与其他编程语言一样&#xff0c;有良好的注释部分&#xff0c;会让你的程序在后续的改进或优化中&#xff0c;变得便利。同时&#xff0c;给自己培养了良好的编程习惯。 在Python语言中&#xff0c;有两种注释方法。 1.单行…

DAY 43 Apache的配置与应用

虚拟Web主机 概述 虚拟web主机指的是在同一台服务器中运行多个web站点&#xff0c;其中每一个站点实际上并不独立占用整个服务器&#xff0c;因此被称为"虚拟"web主机。通过虚拟web主机服务可以充分利用服务器的硬件资源&#xff0c;从而大大降低网站构建及运行成本…

API 接口主流协议有哪些? 如何创建不同协议?

API 接口协议繁多&#xff0c;不同的协议有着不同的使用场景。70% 互联网应用开发者日常仅会接触到最通用的 HTTP 协议&#xff0c;相信大家希望了解更多其他协议的信息。我们今天会给大家介绍各种 API 接口主流协议和他们之间的关系。 1、API 接口主流协议有哪些? 接口协议分…

理解websocket连接的原理

背景 Websocket是一个持久化的协议&#xff0c;相对于HTTP这种非持久的无状态协议来说 一、问题 http long poll&#xff0c;或者ajax轮询都可以实现实时信息传递&#xff0c;为什么还需要websocket&#xff1f; 二、理解 ajax轮询&#xff1a;浏览器隔个几秒就发送一次请求&am…

json for modern c++

目录 json for modern c概述编译问题问题描述问题解决 读取JSON文件demo json for modern c GitHub - nlohmann/json: JSON for Modern C 概述 json for modern c是一个德国大牛nlohmann写的&#xff0c;该版本的json有以下特点&#xff1a; 1.直观的语法。 2.整个代码由一个…

Spring项目创建与 Spring Bean 的存储与读取

目录 一、创建Spring项目 1.1 创建Maven项目 1.2 添加 Spring 框架依赖 1.3 添加启动类 二、Bean对象的创建与存储 2.1 创建Bean 2.2 将Bean注册到容器 2.3 获取并使用Bean对象 2.3.1 创建Spring上下文 2.3.2 从Spring容器中获取Bean对象​编辑 延申&#xff08;多种…

政企数智办公巡展回顾 | 通信赋能传统行业数智化转型的应用实践

在宏观政策引导、技术革新与企业内部数字化改革需求的共同驱使下&#xff0c;数智办公已经成为各行各业转型升级的必由之路。关注【融云 RongCloud】&#xff0c;了解协同办公平台更多干货。 近期&#xff0c;“连接无界 智赋未来” 融云 2023 政企数智办公巡展在北京、杭州相…

X进制转十进制黄金万能算法

单纯、混合进制通吃&#xff0c;真正的黄金万能的进制转换方法。 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大咖免费“圣经”教程《 python 完全自学教程》&#xff0c;不仅仅是基础那么简单…… 地址&#xff1a;https:/…