【数据结构】 -- 堆 （堆排序）（TOP-K问题）

引入

要学习堆，首先要先简单的了解一下二叉树，二叉树是一种常见的树形数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。它具有以下特点：

  1. 根节点（Root）：树的顶部节点，没有父节点。
  2. 子节点（Children）：每个节点最多有两个子节点，分别称为左子节点和右子节点。
  3. 叶子节点（Leaf）：没有子节点的节点称为叶子节点。
  4. 父节点（Parent）：每个节点都有一个父节点，除了根节点。
  5. 深度（Depth）：从根节点到某个节点的唯一路径的长度，根节点的深度为0。
  6. 高度（Height）：从某个节点到它的最远叶子节点的路径长度，叶子节点的高度为0。
  7. 遍历（Traversal）：遍历二叉树是指按照一定顺序访问树中的每个节点，常见的遍历方式包括前序遍历、中序遍历和后序遍历。

二叉树的应用非常广泛，在后面我会详细介绍。

满二叉树：除了叶子结点外，每个结点都有两个子结点

一个深度为k的满二叉树有2的k次方减一个节点。

完全二叉树：除了最底层可能不是满的外，其它每一层从左到右都是满的。

满二叉树是完全二叉树的子集，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 

堆就是一种完全二叉树。

二叉树的储存

逻辑结构和物理结构

逻辑结构和物理结构是计算机科学中两个重要的概念，它们描述了数据在计算机中的不同组织方式。

  1. 逻辑结构：

    • 逻辑结构是指数据元素之间的相互关系和操作规则。它关注的是数据之间的逻辑关联，而不考虑数据在计算机内部的存储方式。
    • 常见的逻辑结构包括线性结构、树形结构和图形结构。
    • 线性结构中的数据元素之间是一对一的关系，例如线性表、栈、队列等。
    • 树形结构中的数据元素之间存在一对多的关系，例如二叉树、B树等。
    • 图形结构中的数据元素之间是多对多的关系，例如图、网络等。

  2. 物理结构：

    • 物理结构描述了数据在计算机内部存储的方式和组织形式，也称为存储结构。
    • 物理结构与计算机的存储器相关，它包括了数据元素在内存中的存储位置和存储方式。
    • 常见的物理结构包括顺序存储结构和链式存储结构。
    • 顺序存储结构是将数据元素连续地存储在内存中的一块连续的存储空间中，例如数组。
    • 链式存储结构是通过指针将数据元素存储在内存中的不同位置，并通过指针将它们串联起来，例如链表。

逻辑结构关注数据之间的逻辑关系和操作规则，而物理结构关注数据在计算机内部的实际存储方式和组织形式。

二叉树的储存

二叉树有多种存储方式，常见的包括顺序存储和链式存储。

  1. 顺序存储： 顺序存储通常使用数组来表示二叉树。假设树的根节点存储在数组下标为0的位置，则对于任意一个下标为i的节点：

    • 其左子节点的下标为2i + 1
    • 其右子节点的下标为2i + 2 例如，如果要存储二叉树的节点值为[1, 2, 3, 4, 5, 6, 7]的完全二叉树，可以使用数组[1, 2, 3, 4, 5, 6, 7]进行存储。

  2. 链式存储： 链式存储则是通过节点之间的引用来表示二叉树的结构，每个节点包含数据域和左右子节点指针域。

链式储存我们放在后边更新，在这里我们先学习顺序储存。

顺序储存

顺序储存用数组来储存，顺序存储一般只适合用来存储完全二叉树（堆），用顺序储存再存储非完全的二叉树会存在空间浪费

 堆的实现

头文件：

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int HPDatatype;typedef struct Heap
{HPDatatype * a;int size;int capacity;}HP;//初始化
void HPInit(HP* php);//插入数据
void HPPush(HP* php, HPDatatype x);//交换
void Swap(HPDatatype* a,HPDatatype * b);//销毁
void HPDestroy(HP* php);//向上调整
void AdjustUp(HPDatatype* a, int child);//向下调整
void AdjustDown(HPDatatype* a,int n, int parent);//删除顶部数据
void HPPop(HP* php);//返回顶部数据
HPDatatype* HPTop(HP* php);//判空
bool HPEmpty(HP* php);

实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"// 初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;}//插入数据
void HPPush(HP* php, HPDatatype x)
{assert(php);//判断空间够不够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDatatype* tmp = (HPDatatype* )realloc(php->a,newcapacity * sizeof(HPDatatype));if (tmp == NULL){perror("realloc fail");exit(-1);}php->capacity = newcapacity;php->a = tmp;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}//交换
void Swap(HPDatatype* a, HPDatatype* b)
{HPDatatype cmp = *a;*a = *b;*b = cmp;
}//销毁
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}//向上调整
void AdjustUp(HPDatatype* 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(HPDatatype* a, int n, int parent)
{int child = 2 * parent + 1;//先假设左边的小while (child < n){if (child + 1 < n && a[child + 1] < a[child])//规避chlid + 1 越界的风险{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}//删除顶部数据
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--; AdjustDown(php->a, php->size,0);
}//返回顶部数据
HPDatatype* HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

TOP-K问题

一般来说，堆分为两类

  1. 大堆（Max Heap）：在最大堆中，每个节点的值都大于或等于其子节点的值。换句话说，堆顶部的元素是整个堆中的最大值。最大堆常用于实现优先队列，其中具有最高优先级的元素始终位于堆顶。

  2. 小堆（Min Heap）：在最小堆中，每个节点的值都小于或等于其子节点的值。因此，堆顶部的元素是整个堆中的最小值。最小堆也常用于优先队列，其中具有最低优先级的元素位于堆顶。

简单来说大堆中，同一个分支中大的在上；小堆中，同一分支小的在上。

在这里以小堆为例：

向上调整算法

往堆中插入一个数据时，先将插入的数据放到堆的最后一个节点，然后利用向上调整算法依次调整。

图示：

只要子节点不越界循环一直进行，当字节点不小于父节点时跳出if()语句进入else，跳出循环。

//向上调整
void AdjustUp(HPDatatype* 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;}}
}

求一堆数据(储存在小堆中)中最最小的前几个数据：将数据插入堆中，小堆的堆顶中储存的就是堆中最小的数据，把堆顶的数据取下来，再将堆顶的数据释放；用向上调整算法调整堆，再依次取堆顶，重复。

//TOP-K
void HPtest02()
{int a[] = { 5,6,1,4,2,8 };HP s;HPInit(&s);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&s, a[i]);}int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&s));HPPop(&s);}HPDestroy(&s);
}int main()
{HPtest02();return 0;
}

 演示：

在TOP-K问题中，我们会发现，输出的数据是按顺序拍好的，那么我们可不可以在此基础上进行排序呢。 把数据储存到堆中之后，再依次拿出来。

//排序
void HPtest03()
{int a[] = { 5,6,1,4,2,8 };HP s;HPInit(&s);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&s, a[i]);}int i = 0;while (!HPEmpty(&s)){a[i++] = HPTop(&s);HPPop(&s);}HPDestroy(&s);
}
int main()
{HPtest03();return 0;
}

这样我们就可以对数据进行排序。

这个算法的时间复杂度非常低 。 一个有k个节点的对的深度为log（k），一条分支最多交换log (k) - 1次，所以

算法的时间复杂度为log N。 但是这并不能称作真正的排序，因为它在原数组的基础上开辟了新的空间。

堆排序

建堆算法

//堆排序
void HeapSort(int* a, int n)
{//建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}
}void Heaptset()
{int a[] = { 5,6,8,4,1,2,3 };HeapSort(a, 7);
}
int main()
{//HPtest01();/*HPtest02();*///HPtest03();Heaptset();return 0;
}

排序

在惯性思维中，要排降序应该会建大堆，排升序会建小堆。但这样会导致一个问题（以建排降序 为建小堆为例）

小堆的堆顶为这组数据中最小的数，我们将它取出，作为排序的第一个数

取出堆顶后，找出第二小的数据， 但是此时的堆各个节点已经不满足之前的大小关系了，4之前是6和5的父节点，比6和5大，但是与2为兄弟节点，兄弟节点之间的大小关系原来并不清楚，无法直接找出第二大的数据（可以重新把剩下的数据建堆，但是没必要，时间成本大）。在堆排序中不能让第一个数据直接拿出去，这样会改变节点之间的父子关系，不能确定大小关系，无法找出需要的节点。

接下来以排降序排降序为例演示过程。

//堆排序
void HeapSort(int* a, int n)
{//建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}void Heaptset()
{int a[] = { 5,6,8,4,1,2,3 };HeapSort(a, 7);
}
int main()
{//HPtest01();/*HPtest02();*///HPtest03();Heaptset();return 0;
}

调试：

向下调整算法的时间复杂度为log N,堆排序在最坏的情况下N个数据要排N次，所以堆排序的时间复杂度为N log N。可以极大的提高程序的效率。

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

idea如何根据路径快速在项目中快速打卡该页面

idea如何根据路径快速在项目中快速打卡该页面

在idea项目中使用快捷键shift根据路径快速找到该文件并打卡 双击shift(连续按两下shift) -粘贴文件路径-鼠标左键点击选中跳转的路径 自动进入该路径页面 例如&#xff1a;我的实例路径为src/views/user/govType.vue 输入src/views/user/govType或加vue后缀src/views/user/go…
阅读更多...
Cweek4+5

Cweek4+5

C语言学习 十.指针详解 6.有关函数指针的代码 代码1&#xff1a;(*(void (*)())0)(); void(*)()是函数指针类型&#xff0c;0是一个函数的地址 (void(*)())是强制转换 总的是调用0地址处的函数&#xff0c;传入参数为空 代码2&#xff1a;void (*signal(int, void(*)(int))…
阅读更多...
以客户为中心：消费电子行业的产品研发之道

以客户为中心：消费电子行业的产品研发之道

在消费电子行业这片快速变化的领域中&#xff0c;产品的迭代更新和技术的创新是推动行业不断前进的动力。然而&#xff0c;随着市场的日益成熟和消费者需求的多样化&#xff0c;如何确保产品能够满足目标用户的需求&#xff0c;成为摆在每一个产品研发团队面前的难题。本文将探…
阅读更多...
JVM垃圾收集器和性能调优

JVM垃圾收集器和性能调优

目标&#xff1a; 1.JVM垃圾收集器有哪几种&#xff1f; 2.CMS垃圾收集器回收步骤。 一、JVM常见的垃圾回收器 为什么垃圾回收的时候需要STW? 标记垃圾的时候&#xff0c;如果不STW&#xff0c;可能用户线程就会不停的产生垃圾。 1.1 单线程收集 Serial和SerialOld使用单…
阅读更多...
如何下载BarTender软件及详细安装步骤

如何下载BarTender软件及详细安装步骤

BarTender是美国海鸥科技推出的一款优秀的条码打印软件&#xff0c;应用于 WINDOWS95 、 98 、 NT 、 XP 、 2000 、 2003 和 3.1 版本&#xff0c; 产品支持广泛的条形码码制和条形码打印机&#xff0c; 不但支持条形码打印机而且支持激光打印机&#xff0c;还为世界知名品牌条…
阅读更多...
基于R语言BIOMOD2 及机器学习方法的物种分布模拟与案例分析

基于R语言BIOMOD2 及机器学习方法的物种分布模拟与案例分析

原文链接&#xff1a;基于R语言BIOMOD2 及机器学习方法的物种分布模拟与案例分析https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247606139&idx4&snf94ec30bfb5fa7ac0320403d49db3b66&chksmfa821e9ccdf5978a44a9ba96f6e04a121c0bbf63beea0940b385011c0b…
阅读更多...
联合体和枚举＜C语言＞

联合体和枚举＜C语言＞

导言 在C语言中除了结构体外&#xff0c;联合体和枚举也是自定义类型&#xff0c;联合体主要用于节省空间&#xff0c;在同一块内存存储多种类型的数据&#xff0c;而枚举可以提高代码的可读性、可维护性。 联合体&#xff08;union&#xff09; 它还有个更容易理解的名字&…
阅读更多...
力扣2444.统计定界子数组的数目

力扣2444.统计定界子数组的数目

力扣2444.统计定界子数组的数目 观察到不满足条件的数 可以作为天然的分割线 因此在枚举右端点的过程中 预处理minK&#xff0c;maxK和分割线上一次出现的下标 res min(min_i,max_i) - i0; 但是因为可能在到下个区段时 min_i和max_i尚未更新 导致结果为负数 所以要跟0再取一…
阅读更多...
【devops】 Bytebase 一站式开源 数据库DevOps平台

【devops】 Bytebase 一站式开源 数据库DevOps平台

初识 Bytebase 1、安装 安装地址 https://www.bytebase.com/docs/get-started/self-host/#docker 安装指令 docker run --init \--name bytebase \--publish 8080:8080 --pull always \--volume ~/.bytebase/data:/var/opt/bytebase \bytebase/bytebase:2.18.02、登录-dashboa…
阅读更多...
红黑树的介绍与实现

红黑树的介绍与实现

前言 前面我们介绍了AVL树&#xff0c;AVL树是一棵非常自律的树&#xff0c;有着严格的高度可控制&#xff01;但是正它的自律给他带来了另一个问题&#xff0c;即虽然他的查找效率很高&#xff0c;但是插入和删除由于旋转而导致效率没有那么高。我们上一期的结尾说过经常修改…
阅读更多...
为何PHP使用率 大幅度下降！需求量几乎为零！

为何PHP使用率 大幅度下降！需求量几乎为零！

用PHP的人越来越少的主要原因包括&#xff1a;市场竞争加剧、新技术的出现、性能和安全问题、以及开发者社区的变化。市场竞争加剧是其中一个突出的因素。随着Python、Node.js等现代编程语言的崛起&#xff0c;它们提供了更好的性能、更简洁的语法和更丰富的框架&#xff0c;逐…
阅读更多...
技术与业务的完美融合：大数据BI如何真正提升业务价值

技术与业务的完美融合：大数据BI如何真正提升业务价值

数据分析有一点经典案例 沃尔玛的啤酒和尿布案例 开始做BI的时候&#xff0c;大家肯定都看过书&#xff0c;那么一定也看过一个经典的案例&#xff0c;就是沃尔玛的啤酒和尿布的案例。这个案例确实很经典&#xff0c;但其实是一个失败的案例。为什么这么说呢&#xff1f;很明显…
阅读更多...
Spring Boot 实现动态数据源配置

Spring Boot 实现动态数据源配置

前言 之前在CSDN博客以及某站看了教程&#xff0c;不免觉得有点不知如何下手&#xff0c;好在最后融合了以下&#xff0c;得出了一个比较简单的配置动态数据源的过程。 首先项目是Spring Boot的单体项目&#xff0c;我们的需求是要连接多个数据库&#xff0c;那么就需要配置多个…
阅读更多...
Nvidia/算能 +FPGA+AI大算力边缘计算盒子：大疆RoboMaster AI挑战赛

Nvidia/算能 +FPGA+AI大算力边缘计算盒子：大疆RoboMaster AI挑战赛

NVIDIA Jetson TX2助力机器人战队斩获RoboMaster AI挑战赛冠亚军 一个汇聚数百万机器人专家与研究人员的赛场&#xff0c;一场兼具工程、策略和团队挑战的较量&#xff0c;说的正是近日刚刚在澳大利亚布里斯本ICRA大会上闭幕的大疆RoboMaster AI挑战赛今年的冠军I Hiter以及亚军…
阅读更多...
nodejs最新某东h5st(4.7.2)参数分析与javascript逆向纯算法还原（含算法源码）（2024-06-09）

nodejs最新某东h5st(4.7.2)参数分析与javascript逆向纯算法还原（含算法源码）（2024-06-09）

一、作者声明&#xff1a; 文章仅供学习交流与参考&#xff01;严禁用于任何商业与非法用途&#xff01;否则由此产生的一切后果均与作者无关&#xff01;如有侵权&#xff0c;请联系作者本人进行删除&#xff01; 二 、写在前面 h5st从4.1一路更新到4.7.2&#xff0c;逐渐vmp…
阅读更多...
【Redis】什么是Redis缓存 雪崩、穿透、击穿？（一篇文章就够了）

【Redis】什么是Redis缓存 雪崩、穿透、击穿？（一篇文章就够了）

目录 什么是Redis? Redis的正常存储流程&#xff1f; 什么是Redis缓存雪崩&#xff1f; 缓存雪崩 缓存预热 缓存失效时间的随机性 什么是Redis缓存穿透&#xff1f; 缓存穿透 缓存空对象 BloomFilter&#xff08;布隆过滤器&#xff09; 什么是Redis缓存击穿&#…
阅读更多...
VBA高级应用30例应用2实现在列表框内及列表框间实现数据拖动

VBA高级应用30例应用2实现在列表框内及列表框间实现数据拖动

《VBA高级应用30例》&#xff08;版权10178985&#xff09;&#xff0c;是我推出的第十套教程&#xff0c;教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开&#xff0c;这套教程案例与理论结合&#xff0c;紧贴“实战”&#xff0c;并做“战术总结”&#xff0c;以…
阅读更多...
深度学习简单概述

深度学习简单概述

概述 理论上来说&#xff0c;参数越多的模型复杂度越高、容量越大&#xff0c;这意味着它能完成更复杂的学习任务。但复杂模型的训练效率低&#xff0c;易陷入过拟合。随着云计算、大数据时代的到来&#xff0c;计算能力的大幅提高可以缓解训练的低效性&#xff0c;训练数据的…
阅读更多...
大型零售企业总部到分公司数据发放，有没有更优化的方案？

大型零售企业总部到分公司数据发放，有没有更优化的方案？

大型零售企业在市场经济中扮演重要角色&#xff0c;是保证基础商品生产、流通和供给的重要一环。随着企业发展&#xff0c;很多大型零售企业都会在全国、乃至全球各地开设分公司&#xff0c;用以降低生产和运营成本&#xff0c;更好地提供本地化服务。 为了保证总部与分公司间信…
阅读更多...
GAT1399协议分析（9）--图像上传

GAT1399协议分析（9）--图像上传

一、官方定义 二、wirechark实例 有前面查询的基础，这个接口相对简单很多。 请求： 文本化： POST /VIID/Images HTTP/1.1 Host: 10.0.201.56:31400 User-Agent: python-requests/2.32.3 Accept-Encoding: gzip, deflate Accept: */* Connection: keep-alive content-type:…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023