Avl树(有详细图解)

目录

介绍

引入

概念 

特点 

模拟实现

思路

插入

旋转 

左旋

无子树

有子树

右旋

无子树

有子树

左右旋

引入(也就是有子树版本的抽象图解)

解决方法(也就是左右旋) 

总结

无子树(也就是curright的位置就是newnode)

有子树 

模型高度解释

旋转 

更新三个节点的bf

右左旋

无子树

有子树

旋转

更新三个结点的bf

注意点

代码


介绍

引入

map和set的底层都是按照二叉搜索树来实现的

  • 但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N)
  • 因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现

概念 

  • AVL树是一种自平衡二叉搜索树,其名称源自其发明者Adelson-Velsky和Landis
  • AVL树通过确保各个节点之间的高度差不超过1,来保证在最坏情况下,树的高度仍为O(log n) (其中n是树中节点的数量),这样可以保持最好的效率

特点 

  • 自平衡:在插入或删除节点时,AVL树会自动执行旋转操作来保持平衡。这些旋转操作包括左旋、右旋、左右旋和右左旋等,通过这些旋转可以调整节点的平衡因子,使其满足平衡条件(不超过1)

  • 二叉搜索树性质:AVL树仍然是二叉搜索树,即左子树的所有节点的值都小于根节点的值,右子树的所有节点的值都大于根节点的值

模拟实现

思路

插入

  • avl树中保持平衡的关键就在于平衡因子(bf)
  • 这里bf=右子树高度-左子树高度
  • 主要就是每次插入时,需要更新平衡因子 (但只需要沿着newnode的位置往上就行,因为它改变的只是newnode所在那一分支)

  • 只要当前结点bf=0,就可以不再更新了(它此时变为0,说明原来是1/-1)
  • 那么让1/-1变为0,这一分支的高度是不变的,那么以这个为子树的树,高度也不会变,平衡因子也就不变

  • 然后,如果结点bf=2/-2,就要开始旋转了
  • 而旋转分为4种,需要判断cur和cur父亲的bf,来区分使用哪种旋转方式 

  • 旋转后的子树,其根结点bf是0,那么他也是从在插入新结点前的1/-1变成了0,所以也就不需要往上更新了
  • 这样,插入步骤就结束了

旋转 

左旋
无子树

左旋实际上就是 -- ​​​​​​​让p成为cur的左子树,cur的右边不受影响

有子树

  • 虽然都有子树,但我们无法知道到底是多少个,到底是什么形态
  • (这些其实我们都不关心,我们只要知道一个相对大小就行,毕竟重点还是在p和cur上)
  • 有子树和无子树都是差不多的,只不过是多了子树,但是p和cur的bf仍然是2和1,只有这样才会触发左旋
  • 然后设cur左子树高度为h,那么可以推出curright高度就是h+1,p左树是h
  • 旋转后 -- cur的原左子树成为了p的右子树(因为本身curleft就处于p的右树范围),p左树不变,cur右树也不变
  • 只要记住 -- 左旋是p成为cur的左树,那么原左树就成为了p的右树
  • 旋转后的bf:(都为0)
右旋

和左旋非常像,只不过是换了个方向

无子树

旋转后,p成为cur的右子树

有子树

和左旋一个思路,最终得到了这么一副抽象图:

然后就是旋转了 -- cur原右子树成为p的左子树(本身就是p左树范围内),p右子树不变

计算bf后,两个结点的bf变成了0,其他的都不变

两种旋转真的非常像,只要记住左旋是p成为cur的左子树,右旋是p成为cur的右子树,就行了

左右旋
引入(也就是有子树版本的抽象图解)

上面有这样一种情况,它是需要被右旋的:

但是如果这个新结点是在curright下呢???

这种情况不能使用单独的右旋(因为单右旋没有用):

会发现右旋后,这支子树的根结点的bf还是2(只是把原子树的左右颠倒了)

 

解决方法(也就是左右旋) 

然后,我们经过对比可以发现,实际上他和右旋之间就差一个拐拐 :

所以可以考虑将那个拐角处掰正,也就是对应的将cur那支子树进行左旋:

这样,就可以和原来的p拼接起来,达到右旋的条件

最终经过右旋后,就可以完成我们的需求(这里只是抽象演示,并没有细画cur的情况,有子树中会有详细版)

总结

相当于对cur左旋是进行右旋的预热,最终其实还是经过对p右旋完成的 

无子树(也就是curright的位置就是newnode)

先对cur进行左旋,然后对p右旋:

最终newnode(也就是curright成为了这一支子树的根结点)

有子树 

首先,在无子树情况中,我们会发现,最终cur的右结点成为了根,那么我们就需要额外画出这个结点

其次,新结点放在curright的左/右子树都可以,只不过最后处理这三个重要结点的bf时,需要单另处理

先抽象好模型(设curright右子树高度为h,从而可以推出其他高度)

模型高度解释

你可能会好奇,为什么curright的左右子树高度被写成是相等的? (至少我好奇了,然后我画了画,发现是有人家的理由的)

  • 这里还是设右子树高度为h
  • 如果原先左子树高度是h+1(高度差不能超过1嗷)
  • 那新加一个结点就会变成h+2,会让curright的bf变成-2,那么这里不会触发p的左右旋,而是curright的旋转(左旋或者左右旋,具体看新结点的位置)

  • 如果原先左子树高度是h-1(高度差不能超过1嗷)
  • 那新加一个结点就会变成h,会让curright的bf变成0,那bf的更新到curright就停止了,不会让p更新到2/-2,所以依然不可以

那么就可以得到,curright的两个子树(如果有),那一定高度相等,才能触发p的左右旋

旋转 

继续接下来的步骤,抽象好模型后,对cur进行左旋

不要忘记前面介绍的左旋了嗷(这里的cur成为curright的左子树,原左树成为cur的右子树)

然后和p连接在一起(也就是修改p的指向和两个结点的_parent指向)

接下来就是旋转的最后一步辣,对p进行右旋

这里是将p作为curright的右子树,原右子树成为p的左树(都是之前的步骤)

之后就是最重要的一步,对三个结点的bf重新赋值(虽然进行了旋转,但更新到的bf实际并不准确,因为右旋和左右旋用到的模型本身就不同)

更新三个节点的bf

这里的更新也得分情况

像这里用到的图解,是新结点插入在curright的左树部分

(下面是全部的旋转变换过程)

  • 那么由于要对cur左旋的缘故,curright中带有新结点的这一支给了cur的右树,那么cur右边和左边平衡了,cur的bf=0
  • 但p不一样,p的左树是被分配的curright的右树,其高度只有h(注意看图嗷看图),所以p的bf=1

如果新结点插入在curright的右树部分

  • 道理和上面的一样
  • 因为curright的右树给了p的左边:
  • 所以p的bf=0(平衡了)
  • 而cur的右边是原curright的左边,高度是0,所以cur的bf=-1

只要过程熟悉,知道是怎么变的,bf的更新也素手到擒来噜

右左旋

和左右旋非常像,只不过是换了个方向

无子树

同样是有拐,也是一样要把那个拐掰正,也就是对cur进行右旋(让cur成为curleft的右子树)

最后就可以美美对p进行左旋噜

然后curleft成为了这一支的根结点

有子树

由于在左右旋中,我们已经分析了模型高度,所以我们直接画出右左旋的抽象模型(本质一样的)

旋转

接下来就是相似的操作,对curleft进行右旋

然后和p连接

就变成了标准的左旋状态,对p进行左旋:

最后就是:curleft的右结点通过右旋给了cur的左边,左结点经过左旋给了p的右边

更新三个结点的bf

这里用到的图解,是新结点插入在curleft的左树部分

像一直在重复说的那样(臣妾已经说倦了)

  • 因为右旋,cueleft的右子树给了cur的左树,所以cur的左边是h,而右边是自己的h+1,所以cur的bf=1
  • 因为左旋,curleft的左子树给了p的右子树,而右子树正是新结点插入位置,所以p的左边是h+1,右边是原先自己的h+1,相等了,所以p的bf=0

当新结点插入在curleft的右树部分

经过旋转后:

会发现:

  • 新结点所在的右子树,在右旋中给了cur的左子树,所以cur的左右相等了,cur的bf=0
  • 而给p的curleft右树高度仍是h,而p的左子树是自己的h+1,所以p的bf=-1​​​​​​​

注意点

一定要写对插入的逻辑,还有 各种结点指向 / bf数值 的更新,超级重要!!!

  • 亲身经历,本来以为对了,测试也是对的,过了几天加了点测试代码(因为实在是不好看这个代码到底写的对不对,又多又杂),结果就挂了
  • 找了半天的错,发现旋转代码没问题,是我插入里面的"往上更新bf"逻辑错了
  • 我是先一直更新到根结点,然后才找bf=2/-2的结点
  • 就导致,旋转完后子树的bf是对的,它父结点的bf错了,本来就不应该更新它的!(我哭死)

然后就是旋转里面,"原子树根结点的父结点"的指向要注意不要漏掉,要更新啊!!!

其他的好像就没啥了,只要多多写备注,就应该没啥问题

代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cassert>
#include <cstdlib>namespace my_AvlTree
{template <class T>struct AvlTreeNode{AvlTreeNode(const T &data = T()): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AvlTreeNode<T> *_left;AvlTreeNode<T> *_right;AvlTreeNode<T> *_parent;T _data;int _bf; // 节点的平衡因子};// AVL: 二叉搜索树 + 平衡因子的限制template <class T>class AvlTree{typedef AvlTreeNode<T> Node;public:AvlTree(): _root(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T &data);// AVL树的验证bool IsAvlTree(){return _IsAvlTree(_root);}void levelOrder();size_t Height(){return _Height(_root);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAvlTree(Node *root);size_t _Height(Node *root);// 右单旋void RotateR(Node *parent);// 左单旋void RotateL(Node *parent);// 右左双旋void RotateRL(Node *parent);// 左右双旋void RotateLR(Node *parent);private:Node *_root;};template <class T>void AvlTree<T>::levelOrder(){Node *root = _root;std::vector<std::vector<T>> arr;std::queue<Node *> q;if (root != nullptr){q.push(root);}while (!q.empty()){std::vector<T> tmp;  // 存储一层的结点int size = q.size(); // 此时队列内的元素就是上一层的结点个数for (int i = 0; i < size; ++i){tmp.push_back(q.front()->_data);if (q.front()->_left){ // 有子树就放进队列中q.push(q.front()->_left);}if (q.front()->_right){q.push(q.front()->_right);}q.pop(); // 出掉这个父结点}arr.push_back(tmp);}for (auto &i : arr){for (auto &j : i){std::cout << j << " ";}std::cout << std::endl;}}template <class T>bool AvlTree<T>::Insert(const T &data){if (_root == nullptr){_root = new Node(data);}else{Node *cur = _root, *parent = cur, *newnode = nullptr;// 找到插入位置while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else{return false;}}// 插入+改父亲bfnewnode = new Node(data);if (data < parent->_data){parent->_left = newnode;--parent->_bf;newnode->_parent = parent;}else{parent->_right = newnode;++parent->_bf;newnode->_parent = parent;}// std::cout << "parent:" << parent->_data << " "//           << "newnode:" << newnode->_data << std::endl;// 维护bfcur = parent; //注意,这里不能直接定义cur的父结点,因为不能保证cur不为空(如果此时只有俩结点,就为空了!!!)while (cur != _root){Node *pnode = cur->_parent;// 更新bfif (pnode->_left == cur){--pnode->_bf;}else{++pnode->_bf;}// 判断是否继续往上更新if (cur->_bf == 0){break;}else{if (pnode->_bf == 2 || pnode->_bf == -2){// pnode就是不合法的结点,然后判断它该怎么调整if (pnode->_bf == -2 && cur->_bf == -1){// 右单旋RotateR(pnode);}if (pnode->_bf == 2 && cur->_bf == 1){// 左单旋RotateL(pnode);}if (pnode->_bf == -2 && cur->_bf == 1){// 左右双旋RotateLR(pnode);}if (pnode->_bf == 2 && cur->_bf == -1){// 右左双旋RotateRL(pnode);}break;}else{cur = pnode;pnode = pnode->_parent;}}}}return true;}template <class T>bool AvlTree<T>::_IsAvlTree(Node *root){if (root == nullptr){return true;}int left_height = _Height(root->_left);int right_height = _Height(root->_right);if (right_height - left_height != root->_bf) //不要太相信自己写的bf计算方法{std::cout << right_height << std::endl;std::cout << left_height << std::endl;std::cout << root->_bf << std::endl;std::cout << "平衡因子异常" << std::endl;return false;}return abs(right_height - left_height) < 2 && _IsAvlTree(root->_left) && _IsAvlTree(root->_right);}template <class T>size_t AvlTree<T>::_Height(Node *root){if (root == nullptr){return 0;}int leftsize = _Height(root->_left) + 1;int rightsize = _Height(root->_right) + 1;return leftsize > rightsize ? leftsize : rightsize;}template <class T>void AvlTree<T>::RotateL(Node *parent){Node *cur = parent->_right, *curleft = cur->_left, *ppnode = parent->_parent;// 连接cur上需要修改的子树(比如左旋就是让parent当cur的左子树,那么cur左树就得和parent右边相连)if (curleft) // 防止左树为空{curleft->_parent = parent;}parent->_right = curleft;// 连接cur和parentcur->_left = parent;// 修改parent父结点的指向if (ppnode == nullptr) // 如果此时parent是根结点,那么它没有父结点,且需要更新根结点{_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}// 改父结点指向(千万别忘辣!!!)cur->_parent = ppnode;parent->_parent = cur;// 维护bfcur->_bf = parent->_bf = 0;}template <class T>void AvlTree<T>::RotateR(Node *parent){Node *cur = parent->_left, *curright = cur->_right, *ppnode = parent->_parent;// 连接cur上需要修改的子树(右旋就是让parent当cur的右子树,那么cur右树就得和parent左边相连)if (curright) // 防止右树为空{curright->_parent = parent;}parent->_left = curright;// 连接cur和parentcur->_right = parent;// 修改parent父结点的指向if (ppnode == nullptr) // 如果此时parent是根结点,那么它没有父结点,且需要更新根结点{_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}// 改父结点指向cur->_parent = ppnode;parent->_parent = cur;// 维护bfcur->_bf = parent->_bf = 0;}template <class T>void AvlTree<T>::RotateLR(Node *parent){Node *cur = parent->_left, *curright = cur->_right;int bf_comp = curright->_bf; // 用于判断插入结点的左右位置RotateL(parent->_left); // 让cur成为curright的左子树RotateR(parent);        // 让parent成为curright的右子树// curright是旋转后子树的根结点// 最终让curright的左子树给了cur的右子树,curright的右子树给了parent的左子树// if (_Height(curright) == 1)// {//     curright->_bf = 0;//     cur->_bf = 0;//     parent->_bf = 0;// }if (bf_comp == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else{if (bf_comp == -1) // 在curright的左边{// 说明cur的右子树多了1,使其与原先的左子树高度相等// 而parent的左子树是h-1,右子树是原先的hcurright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else if (bf_comp == 1) // 在curright的右边{// 说明parent的左子树多了1,使其与原先的右子树高度相等// 而cur的右子树是h-1,左子树是原先的hcurright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else{assert(false);}}}template <class T>void AvlTree<T>::RotateRL(Node *parent) // 插入结点在curleft的左右子树上其中一个位置{Node *cur = parent->_right, *curleft = cur->_left;int bf_comp = curleft->_bf; // 用于判断插入结点的左右位置RotateR(parent->_right);    // 让cur成为curleft的右子树RotateL(parent);            // 让parent成为curleft的左子树// curleft是旋转后子树的根结点// 最终让原curleft的右子树给了cur的左子树,curleft的左子树给了parent的右子树// if (_Height(curleft) == 1)// {//     curleft->_bf = 0;//     cur->_bf = 0;//     parent->_bf = 0;// }if (bf_comp == 0){curleft->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else{if (bf_comp == -1) // 在curleft的左边{// 说明parent右子树多了1,使其与原先的左子树高度相等// 而cur的左子树是h-1,右子树是原先的hcurleft->_bf = 0;cur->_bf = 1;parent->_bf = 0;}if (bf_comp == 1) // 在curleft的右边{// 说明cur的左子树多了1,使其与原先的右子树高度相等// 而parent的右子树是h-1,左子树是原先的hcurleft->_bf = 0;cur->_bf = 0;parent->_bf = -1;}}}
}

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

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

相关文章

资料分析笔记

统计术语 现期&#xff1a;现在的时间 基期&#xff1a;之前的时间 现期量 基期量 增长量&#xff08;有正负&#xff09; 增长率 【增幅、增速、r】&#xff08;有正负&#xff09; 同比&#xff1a;例&#xff1a;2014年5月 和 2013年5月 环比&#xff1a;例&#xff1a;20…

[Linux入门]---git命令行的基本使用

文章目录 1.git使用gitee仓库创建git使用测试ignore文件 1.git使用 git是一款对文件进行版本控制的软件&#xff0c;gitee、github是基于git软件搭建的网站&#xff0c;是可以对代码进行托管的平台&#xff1b;github是国外的网站&#xff0c;访问慢&#xff0c;不稳定&#xf…

基于微信小程序的高校宿舍信息管理系统设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

【C++入门指南】C如何过渡到C++?祖师爷究竟对C++做了什么?

【C入门指南】C如何过渡到C&#xff1f;祖师爷究竟对C做了什么&#xff1f; 前言一、命名空间1.1 命名空间的定义1.2 命名空间使用 二、C输入、输出2.1 std命名空间的使用惯例 三、缺省参数3.1 缺省参数的定义3.2 缺省参数分类 四、函数重载4.1 函数重载概念4.2 C支持函数重载的…

逻辑漏洞挖掘之XSS漏洞原理分析及实战演练 | 京东物流技术团队

一、前言 2月份的1.2亿条用户地址信息泄露再次给各大公司敲响了警钟&#xff0c;数据安全的重要性愈加凸显&#xff0c;这也更加坚定了我们推行安全测试常态化的决心。随着测试组安全测试常态化的推进&#xff0c;有更多的同事对逻辑漏洞产生了兴趣&#xff0c;本系列文章旨在…

C++QT day11

绘制时钟 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPaintEvent>//绘制事件类 #include <QDebug>//信息调试类 #include <QPainter>//画家类 #include <QTimer>//定时器类 #include <QTime> #include &…

039_小驰私房菜_Camera perfermance debug

全网最具价值的Android Camera开发学习系列资料~ 作者:8年Android Camera开发,从Camera app一直做到Hal和驱动~ 欢迎订阅,相信能扩展你的知识面,提升个人能力~ 一、抓取trace 1. adb shell "echo vendor.debug.trace.perf=1 >> /system/build.prop" 2. …

zaabix实现对nginx监控

本文使用监控模板net.tcp.listen[port]实现监听端口 实验环境&#xff1a; 首先搭建好zabbix-server &#xff0c;zabbix-agenthttps://mp.csdn.net/mp_blog/creation/editor/132622769?spm1001.2014.3001.9457 而后在zabbix-agent主机上下载一个nginx 登录zabbix网站创建主…

你写过的最蠢的代码是?

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页: &#x1f405;&#x1f43e;猫头虎的博客&#x1f390;《面试题大全专栏》 &#x1f995; 文章图文并茂&#x1f996…

Android Treble与Mainline计划:推动Android生态系统的持续改进

Android Treble与Mainline计划&#xff1a;推动Android生态系统的持续改进 1. 引言 1.1 Android操作系统和其复杂的生态系统 Android操作系统作为目前全球最流行的移动操作系统之一&#xff0c;具有庞大而复杂的生态系统。它不仅驱动着数十亿台设备&#xff0c;还支持各种类…

送水订水小程序商城的作用是什么?

桶/瓶装水有很高的市场需求度&#xff0c;除了家庭外&#xff0c;部分办公场几乎每天都会订水且有一定的合作&#xff0c;由于没有空间限制&#xff0c;因此对桶装水商家来说&#xff0c;本地和外地客户都有较高的拓展度&#xff0c;而传统电话、微信私信订购宣传方式低效且不智…

Spring boot原理

起步依赖 Maven的传递依赖 自动配置 Springboot的自动配置就是当spring容器启动后&#xff0c;一些配置类、bean对象就自动存入到IOC容器中&#xff0c;不需要我们手动去声明&#xff0c;从而简化了开发&#xff0c;省去了繁琐的配置操作。 自动配置原理&#xff1a; 方案一…

set和map的学习

文章目录 1.set的原型2.set的成员函数1.构造函数2.代码演示 3.map的原型4.map的成员函数1.构造函数2.代码演示 5.OJ练习1.前K个高频单词2.两个数组的交集3.随即链表的复制 1.set的原型 template <class T, //set::key_typeclass Compare less<T>,…

[JAVAee]Spring MVC

目录 Spring MVC框架 MVC Spring MVC的功能 用户与程序的连接 RequestMapping 指定为Get请求 指定为Post请求 获取参数 单个参数 表单传递多个参数 传递对象 后端参数重命名(后端参数映射) 设置参数必传/非必传 获取JSON对象 获取URL中的参数 上传文件 获取…

Javascript小案例-进度条(配置对象版)

gif演示图&#xff1a; 代码&#xff1a; 进度条(配置对象版).html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"&…

eNSP基础网络学习-v02

一、eNSP 1.什么是eNSP eNSP(Enterprise Network Simulation Platform)是一款由华为提供的免费的、可扩展的、图形化操作的网络仿真工具平台&#xff0c;主要对企业网络路由器、交换机进行软件仿真&#xff0c;完美呈现真实设备实景&#xff0c;支持大型网络模拟&#xff0c;让…

怎样防止员工泄露技术?(十条避免公司泄密的措施)

在当今信息化社会&#xff0c;公司信息的安全性和保密性显得尤为重要。一旦公司信息泄露&#xff0c;不仅会对公司的经营造成严重影响&#xff0c;还可能引发法律纠纷。因此&#xff0c;采取有效的措施来防止公司信息泄露是非常必要的。以下是一些具体的措施&#xff1a; 部署洞…

【1993. 树上的操作】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一棵 n 个节点的树&#xff0c;编号从 0 到 n - 1 &#xff0c;以父节点数组 parent 的形式给出&#xff0c;其中 parent[i] 是第 i 个节点的父节点。树的根节点为 0 号节点&#xff0c;所以 par…

【完全二叉树魔法:顺序结构实现堆的奇象】

本章重点 二叉树的顺序结构堆的概念及结构堆的实现堆的调整算法堆的创建堆排序TOP-K问题 1.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的&#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构…

kafka消费者多线程开发

目录 前言 kafka consumer 设计原理 多线程的方案 参考资料 前言 目前&#xff0c;计算机的硬件条件已经大大改善&#xff0c;即使是在普通的笔记本电脑上&#xff0c;多核都已经是标配了&#xff0c;更不用说专业的服务器了。如果跑在强劲服务器机器上的应用程序依然是单…