扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 宝典简介

    • 数据结构和算法(Golang实现)
    • 前言
  • 简单入门Golang

  • 基础知识

  • 常见数据结构

  • 排序算法

  • 查找算法

  • 参考

扫码订阅《 》或入驻星球,即可阅读文章!

左偏树


hunterhug

最小堆/最大堆如果两个堆进行合并,时间复杂度较高,左偏树是可合并的二叉堆,首先满足所有的堆的性质,其外,各种操作时间复杂度都是O(logN)。

左偏树的树节点需要保存的信息有:

1.左右子树节点编号
2.此节点到有空子结点的最短距离len(空子节点的节点,就是子节点数不足2个的节点)
3.自身权值


左偏就是每个节点的左子节点的len不小于右子节点的len(但并不代表左子节点数一定不小于右子节点数),那么可知左偏树中一个节点的距离就是右儿子距离+1(或没有右儿子),且左右子树都是左偏树。

合并树A和树B的操作方法如下: 

1.如果A或B有一个是空树,返回另一个。 
2.如果A的优先级比B低,交换A,B。(确保左堆根节点小于右堆根节点) 
3.递归处理,将B和A的右子树合并。(B,Right(A)递归处理) 
4.如果合并过后A的右儿子距离大于A的左儿子,交换A的左右儿子。(确保左儿子距离大于右儿子) 
5.更新A的距离。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

左偏树合并操作合并的是两棵左偏树,对于堆的插入,就是合并一棵树和一个节点,对于堆的删除,就是合并根的两棵子树。

赞赏支持

如果你觉得文章不错,请打个赏吧!