用jsp做的网站需要什么工具,小程序开发费用分析,制作图片的免费软件,网站建设征求意见稿前言 本篇博客我们来仔细说一下二叉树顺序存储的堆的结构#xff0c;我们来看看堆到底如何实现#xff0c;以及所谓的堆排序到底是什么 #x1f493; 个人主页#xff1a;普通young man-CSDN博客 ⏩ 文章专栏#xff1a;数据结构_普通young man的博客-CSDN博客 若有问题 评… 前言 本篇博客我们来仔细说一下二叉树顺序存储的堆的结构我们来看看堆到底如何实现以及所谓的堆排序到底是什么 个人主页普通young man-CSDN博客 ⏩ 文章专栏数据结构_普通young man的博客-CSDN博客 若有问题 评论区见 欢迎大家点赞收藏⭐文章 目录
树的概念
二叉树的概念及结构
二叉树的基本定义
二叉树的性质
特殊的二叉树类型
存储结构
操作与遍历
堆
堆的实现
堆实现的接口
Heap_Init-初始化
IF_Add_capacity-扩容
Swap-数据交换
Heap_Push-插入
Upward-向上调整
编辑
Heap_Pop-删除
Downward-向下调整
编辑
Heap_Empty-判空
Heap_Top-获取堆顶数据
Heap_Destory-销毁
堆排序
函数部分
Heap_qsort
top-k问题
Top-K问题的基本概念
解决Top-K问题的常见方法
应用实例
问题 树的概念
在学习堆这个数据结构的时候我们先来了解一下什么是树
树是一种重要的非线性数据结构它模拟了自然界中树木的结构不过在计算机科学中树是倒置的即根在上叶在下。树主要由节点或称为结点和边组成用于表示具有层次关系的数据集合。 注意树的结构子树之间没有交际否则就不成立 定义 树是由一个或多个节点组成的有限集合。如果树为空称为空树如果不为空则满足以下条件 有且仅有一个称为根root的节点它没有前驱节点即父节点。除根节点外其余每个节点有且仅有一个父节点。节点的子节点之间没有顺序关系但每个子节点都可视为一个子树。树中的节点数可以是任意有限个包括0空树。 节点的度 一个节点的度是指它拥有子节点的数量。叶子节点或终端节点是度为0的节点即没有子节点的节点。 树的度 树的度是树中所有节点的度中的最大值。 层次与高度 节点的层次是从根节点到该节点路径上的边数。根节点的层次为1。树的高度或深度是树中所有节点的层次中的最大值也就是从根到最远叶子节点的边数。 祖先与后代 对于非根节点从该节点到根节点路径上的所有节点包括根节点都是该节点的祖先。一个节点的后代包括它所有的子节点、子节点的子节点等直至叶子节点。 兄弟节点 具有相同父节点的节点互为兄弟。 子树 任何节点及其所有后代节点构成的树称为该节点的子树。 二叉树的概念及结构
接下来我们介绍树中的一种结构二叉树
二叉树是一种特殊的树形数据结构其中每个节点最多只有两个子节点通常被称作左子节点和右子节点。这种结构使得二叉树成为计算机科学中研究和应用非常广泛的数据结构之一。下面是关于二叉树的一些核心概念和结构特征 二叉树的基本定义
节点二叉树的基本组成单位每个节点可以包含一个数据元素以及指向其左右子节点的引用。根节点树的顶端节点没有父节点。叶子节点没有子节点的节点。度节点的子节点数量二叉树中节点的度不超过2。父子关系与兄弟关系与一般树相同每个节点除了根有唯一的父节点同一父节点的子节点互为兄弟。
二叉树的性质
有序性二叉树的子节点分为左子树和右子树这给树带来了顺序区别于无序的多叉树。递归定义一个空集构成空二叉树或者由一个根节点加上左右两个互不相交的二叉树左子树和右子树组成。
特殊的二叉树类型
满二叉树所有非叶子节点都有两个子节点且所有叶子节点都在同一层。完全二叉树除了最后一层每一层都是满的且最后一层的叶子节点都尽可能靠左排列。二叉排序树BST左子树所有节点的值小于根节点的值右子树所有节点的值大于根节点的值且左右子树也分别是二叉排序树。 存储结构
顺序存储对于完全二叉树可以使用数组来紧凑存储利用数组索引来体现节点间的父子关系。链式存储更通用的方法每个节点包含数据和指向左右子节点的指针通常使用结构体或类来定义节点结构。 操作与遍历
遍历访问二叉树中所有节点的过程有前序遍历、中序遍历、后序遍历和层序遍历等方法。插入与删除在二叉排序树中根据节点值的比较进行插入或删除操作并保持二叉排序树的性质。
二叉树因其结构简单、操作方便常被用于实现各种高效算法如查找、排序、图的遍历等。在实际应用中通过选择特定类型的二叉树如AVL树、红黑树可以达到平衡性和高效的查询性能。
现实中的二叉树 现在我们了解二叉树的一个概念我们接下来进入正题
堆
其实堆我们的堆就是二叉树当中的完全二叉树现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
堆我们分两种大堆 和 小堆 大堆 在大堆中每个节点的值都大于或等于其子节点的值。换句话说父节点总是大于或等于其孩子节点。堆顶元素根节点因此是整个堆中的最大值。 小堆 与大堆相反小堆中的每个节点的值都小于或等于其子节点的值。这意味着父节点总是小于或等于其孩子节点堆顶元素根节点是整个堆中的最小值。 请看这张图 大家知道我们的数据在内存中是b存储结构的模式(物理存储)但是二叉树是a的逻辑结构我们的计算机会通过一种叫映射的方式将这种逻辑结构映射到物理存储。
可能大家会有疑问为什么不直接用数组而要用堆这个结构 数组是一种基础且灵活的数据结构适合存储和访问连续的数据块特别是在索引访问和随机访问方面表现优秀。然而在某些特定场景下尤其是涉及到动态调整数据顺序、维护数据的某种特定排序状态或高效地获取最大值/最小值时数组的效率可能不如专门设计的数据结构比如堆。
堆是一种特殊类型的完全二叉树它具有以下特点使其在某些应用场景下比简单的数组更加高效和适用 维护有序性 最大堆每个节点的值都大于或等于其子节点的值堆顶元素始终是最大值。最小堆每个节点的值都小于或等于其子节点的值堆顶元素始终是最小值。 这种特性使得堆在需要频繁查找最大或最小元素的场景如优先队列中极为高效无需遍历整个数组即可快速获得。 动态调整 堆支持插入和删除元素的同时能够高效地通常是O(log n)时间复杂度重新调整结构以维持其特性这一点在使用数组时难以直接高效实现。 内存利用率 实际实现时堆可以采用数组来存储虽然逻辑上是树状结构但实际上占用的是连续内存空间因此内存使用相对高效。 排序应用 堆可以作为实现堆排序的基础这是一种不稳定的排序算法其优势在于能够提供较好的最坏情况和平均时间复杂度O(n log n)并且不需要像快速排序那样依赖于数据的初始分布。 堆的实现
先看一下堆的结构咋写其实和顺序表的结构一样因为堆本身就是数组只是逻辑看起不是。
//堆的结构
typedef int HeapTypeData;
typedef struct heap
{HeapTypeData* a;int top;int capacity;
}heap;记住这张图
堆实现的接口
//初始化
void Heap_Init(heap* obj);
//插入
void Heap_Push(heap* obj, HeapTypeData x);
//删除
void Heap_Pop(heap* obj);
//判空
bool Heap_Empty(heap* obj);
//获取堆顶
HeapTypeData Heap_Top(heap* obj);
//销毁
void Heap_Destory(heap* obj);
//扩容
void IF_Add_capacity(heap* obj);
//向上调整
void Downward(HeapTypeData* p, int n, int parent);
//向下调整
void Upward(HeapTypeData* p, int child);
//交换
void Swap(HeapTypeData* p1, HeapTypeData* p2);
这些接口是如何实现的嘞如何才能创建这么一棵树 这些接口我会讲解一些没见过德接口因为这个堆的接口和顺序表差不多
Heap_Init-初始化
//初始化
void Heap_Init(heap* obj) {obj-a NULL;obj-top obj-capacity 0;
}
初始化和顺序表差不多将指针置NULL其他的值初始化为0
IF_Add_capacity-扩容
//扩容
void IF_Add_capacity(heap* obj) {if (obj-top obj-capacity){int new_capeccity obj-capacity 0 ? 4 : obj-capacity * 2;HeapTypeData* tmp (HeapTypeData*)realloc(obj-a,sizeof(HeapTypeData) * new_capeccity);if (tmp NULL){assert(realloc);}obj-a tmp;obj-capacity new_capeccity;}
}
Swap-数据交换
//交换
void Swap(HeapTypeData* p1, HeapTypeData* p2)
{HeapTypeData tmp *p1;*p1 *p2;*p2 tmp;
}
Heap_Push-插入
//插入
void Heap_Push(heap* obj, HeapTypeData x) {assert(obj);IF_Add_capacity(obj);obj-a[obj-top] x;obj-top;//这个时候我们需要向上Upward(obj-a,obj-top-1);
}
Upward-向上调整
//向上调整
void Upward(HeapTypeData*p, int child){//通过计算找父母HeapTypeData parent (child - 1) / 2;while (child 0){if (p[child] p[parent]){//交换Swap(p[child], p[parent]);//交换后将parent的位置给给child继续计算下一个parentchild parent;parent (child - 1) / 2;}else{break;}}
} eapTypeData *p: 指向堆数组的指针这个数组存储了堆的所有元素。int child: 插入新元素的位置索引从0开始计数。新插入的元素被认为是一个“孩子”节点该函数会检查并调整这个孩子节点与其父节点的关系以确保堆的性质不变。 函数执行流程 计算父节点位置首先根据孩子节点的索引child计算出其父节点的索引parent公式为(child - 1) / 2。循环比较并交换进入一个循环在循环中不断比较当前孩子节点和其父节点的值。如果孩子节点的值小于父节点的值对于最小堆而言则交换这两个节点的值。这是因为最小堆要求父节点的值不大于子节点的值。更新索引并继续在交换之后原来的子节点变成了新的父节点因此需要更新child为parent同时基于新的child计算新的parent继续进行比较和可能的交换直到孩子节点不再小于其父节点或者到达了堆的根部即child 0时。退出循环一旦发现孩子节点不小于其父节点或者已经没有父节点可比较即到达了树的根循环结束此时堆的性质已经得到恢复。 Heap_Pop-删除
//删除
void Heap_Pop(heap* obj) {assert(obj);assert(obj-a);assert(obj-top 0);//先交换如果直接删除堆顶的数据就会导致血脉混乱Swap(obj-a[0], obj-a[obj-top - 1]);//最后--top就删掉最后一个数据obj-top--;//这边要考虑一个问题我们是小堆但是我们的最大的数在堆顶所以这里需要将最大的数向下移动让次小的数往上补Downward(obj-a,obj-top,0);
}
Downward-向下调整
//向下调整
void Downward(HeapTypeData* p,int n, int parent) {//计算出左儿子int child parent * 2 1;while (child n){if(child 1 n p[child1] p[child]) {//如果右儿子小于左儿子直接到右儿子的位置child;}if ( p[child] p[parent])//如果childparent就交换,要把小的往上走{//这边操作一样算法不同Swap(p[child],p[parent]);parent child;child parent * 2 1;}else{break;}}
} HeapTypeData *p: 指向堆数组的指针。int n: 堆中有效元素的数量。在调整过程中只考虑堆的前n个元素。int parent: 当前需要调整的父节点在数组中的索引位置。 函数执行流程 初始化子节点位置首先计算出当前父节点的左孩子的索引child公式为parent * 2 1。循环比较并交换进入循环只要child的值小于n表示还有子节点可以比较。 选择较小的子节点如果右孩子存在即child 1 n且右孩子的值小于左孩子的值则将child更新为右孩子的索引因为我们要找到两个子节点中更小的那个。比较并交换如果找到的子节点child的值小于其父节点parent的值说明违反了最小堆的性质这时需要交换它们的值并将当前的child位置作为新的父节点位置继续向下比较。更新位置交换后原child位置已成为新的父节点位置因此更新parent child并基于新的父节点重新计算其左孩子的索引child parent * 2 1继续循环。退出条件如果子节点不小于父节点或者已经没有更多的子节点可比较即child n则跳出循环。结束循环结束后堆的性质得到了恢复即以parent为根的子树满足最小堆的定义。 Heap_Empty-判空
//判空
bool Heap_Empty(heap* obj) {assert(obj);return !obj-top;
}
Heap_Top-获取堆顶数据
//返回堆顶
HeapTypeData Heap_Top(heap* obj) {assert(obj);assert(obj-a);return obj-a[0];
}
Heap_Destory-销毁
//销毁
void Heap_Destory(heap* obj) {if (obj-a){free(obj-a);obj-a NULL;obj-capacity obj-top 0;}
}
堆排序
//堆排序
void Heap_qsort(int *p,int sz) {建堆//for (int i 1; i sz; i)// Upward(p,i);//}//建堆for (int i (sz-1-1)/2; i 0; i--)//找最后一个不是叶子的节点{Downward(p,sz,i);}//对堆排序int end sz - 1;while (end 0){Swap(p[0],p[end]);Downward(p,end,0);--end;}
}
int main() {int a[] {5,8,9,2,1};int sz sizeof(a) / sizeof(a[0]);//text1();Heap_qsort(a,sz);int n 3;for (int i 0; i n; i){printf(%d , a[i]);}return 0;
} 函数部分 Heap_qsort 输入参数: int *p: 指向待排序数组的指针。int sz: 数组的大小即元素数量。 过程: 建堆: 与传统从第一个非叶节点开始构造堆的方法不同这里采用了从最后一个非叶节点开始逆序遍历至根节点的方式来构建最小堆。这样做的目的是直接通过Downward函数递归调整每个子树为最小堆最终整个数组构成一个最小堆。计算最后一个非叶节点的索引公式为(sz-1-1)/2然后从这个索引开始逐步向前执行Downward操作。(sz-1-1)/2sz-1-最后一个元素sz-1-1找到父节点堆排序: 首先将堆顶元素数组中的最小值与数组末尾元素交换确保当前最小值位于正确的位置即数组末尾。然后因为堆顶元素现在是数组的末尾元素已经正确排序所以缩小堆的有效大小end - 1并在剩下的元素中再次调用Downward函数调整剩余元素为最小堆。这个过程重复直到整个数组都被正确排序。 输出: 数组p的内容将会按照升序排列。 这边我用gif来展示堆排序的逻辑 这边我建的是一个小堆 排序 那这个堆排序的时间复杂度是多少嘞 那我们就来算一算 得出结论是n*logn
这里面得计算也可以套公式
top-k问题
Top-K问题是一类在大数据集或流式数据中寻找或维护最顶尖最大或最小K个元素的问题。这类问题广泛应用于各种场景特别是在需要高效地处理大量数据并提取关键信息时比如数据分析、推荐系统、搜索引擎排名、社交网络分析、金融风控、大数据处理等领域。
Top-K问题的基本概念
在最简单的形式中Top-K问题可以表述为给定一个包含N个元素的无序集合找出其中最大的K个元素或最小的K个元素。这里的“最大”或“最小”可以根据具体应用需求定义比如数值大小、频率、相关性等。
解决Top-K问题的常见方法 快速选择算法基于快速排序的选择算法变体通过一次划分过程确定一个基准元素的位置如果基准元素恰好处于第K个位置则找到答案否则在基准元素的正确一侧递归继续查找。 堆方法维护一个大小为K的小顶堆找最大K个元素或大顶堆找最小K个元素遍历数据时比较堆顶元素与当前元素如果满足条件则替换堆顶元素并调整堆结构保证堆的性质。这种方法的时间复杂度接近O(N log K)。 二分查找法适用于能够计算数组中某个值排名或能够估算某个值排名的场景。通过二分查找确定一个阈值然后统计小于或大于该阈值的元素个数逐步逼近目标K值。 桶排序或计数排序对于数据范围有限且分布均匀的情况可以将数据分布到有限数量的桶中然后从桶中找出Top-K元素。适合特定场景下提高效率。
应用实例 搜索引擎在搜索引擎中为了提供最相关的网页给用户搜索引擎会根据页面质量、关键词匹配程度等因素对网页进行评分然后选择评分最高的K个网页展示给用户。 推荐系统电商平台或社交媒体平台会根据用户的浏览历史、购买行为、喜好等数据计算商品或内容的相关性分数选出评分最高的K个商品或内容推荐给用户。 大数据分析在处理大规模日志数据时可能需要找出访问量最大的K个IP地址、最常见的K个错误类型等以帮助识别异常或优化资源分配。 金融风控银行和金融机构利用Top-K分析来识别潜在的高风险交易比如监测账户中交易额最大的K笔交易以发现可能的洗钱活动。
Top-K问题因其高效性和实用性在现代信息技术领域扮演着重要角色。
问题
现在你在面试面试官要你找出10亿得数据中最大得前十个你该咋找或许你会说直接用刚才得堆排序这当然可以。 那假如面试官让你用1MB的空间去找这个个数中最大十个嘞
大家或许就有一点懵逼了吧哈哈哈
看图 于是我们的代码就可以这样写
//实现创建x(整形)个数据的一个文件利用1MB空间在x数据中找最大的前n个#includetime.h
//造数据
void Make_data() {int n 100000;srand((unsigned int)time(NULL));const char* date Date.txt;FILE* write fopen(date,w);if (write NULL){assert(fopen);return;}//将数据写入文件for (int i 0; i n; i){int ret (rand() i) % n;//i 防止重复值i是不断变化的%n 控制范围fprintf(write,%d\n,ret);//将生成的数据不断的插入 Date.txt文件中}fclose(write);
}//建堆
//数据量大
Make_heap() {int n 0;printf(请输入你要查看的前几个数);scanf(%d,n);//创建一个空间int* New_node (int*)malloc(n*sizeof(int));if (New_node NULL){assert(malloc);return;}//将数据从文件中读出const char* write Date.txt;FILE* read fopen(write,r);if (read NULL){assert(fopen);return;}//先把进n个数据for (int i 0; i n; i){fscanf(read,%d, New_node[i]);}//建堆sfor (int i (n-1-1)/2; i 0; i--){Downward(New_node,n,i);}//比较剩下的数据依次int end 0;while (fscanf(read,%d,end) 0)//这里会返回EOF(-1){//判断if (end New_node[0]) {//如果endNewnode[0]位置的数直接将这个位置的值赋值New_node[0] end;//再进行向下调整得到小堆Downward(New_node,n,0);}}fclose(read);Heap_qsort_print(New_node,n);
}
Heap_qsort_print(int* p, int n) {//排序从大到小int new_size n - 1;while (new_size 0){Swap(p[0], p[new_size]);Downward(p, new_size, 0);--new_size;}//输出printf(最大的%d个数: , n);for (int i 0; i n; i){printf(%d , p[i]);}
}
int main() {//设置时间戳//Make_data();//建堆Make_heap();} 生成数据: Make_data 函数生成100,000个整数数据并存储到一个名为Date.txt的文件中。每个数据是通过随机数生成器得到并加上循环变量i后取模以避免重复并控制数据范围。 读取并找出Top-N: Make_heap函数首先询问用户想要找出数据文件中的前多少个最大数然后读取文件内容使用最小堆这里实际实现的是一个简化版的维护最大值的过程未完全实现标准的堆结构来维护当前找到的最大N个数。它先读取前N个数构建初始“堆”之后继续读取文件中的剩余数据并与堆顶元素比较若遇到更大的数则替换堆顶元素并重新调整堆。最后使用Heap_qsort_print函数对维护的N个数进行排序并打印。 排序及打印: Heap_qsort_print函数实质上是进行了一个非典型的堆排序操作从堆顶开始每次将堆顶元素当前最大值与末尾元素交换并缩小堆的大小重复此过程直至整个序列变为降序排列最后打印出这N个最大的数。 ok今天的博客就结束了哦
