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

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go视界
    • Go小考
    • Go实战
  • Go资源

    • 优质课程
    • 在线宝典
    • 资源下载
    • 帮找资源
训练营 🔥
  • Go体系课&实战训练营
  • 升值加薪陪跑训练营
Go求职
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
  • 求职服务

    • 内推互助
    • 求职助力
    • 内推公司
Go友会
  • 城市
  • 校园
推广返佣
  • 返佣排行
  • 返佣规则
  • 推广学院
实验区
  • Go周边
  • Go宝典

    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
更多
  • 用户中心

    • 我的信息
    • 我的返佣
    • 我的消息
  • 玩转星球

    • 星球介绍
    • 星主权益
    • 吐槽专区
    • 成长记录
  • 合作交流

    • 商务合作
    • 讲师招募
    • 生态伙伴
author-avatar

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go视界
    • Go小考
    • Go实战
  • Go资源

    • 优质课程
    • 在线宝典
    • 资源下载
    • 帮找资源
训练营 🔥
  • Go体系课&实战训练营
  • 升值加薪陪跑训练营
Go求职
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
  • 求职服务

    • 内推互助
    • 求职助力
    • 内推公司
Go友会
  • 城市
  • 校园
推广返佣
  • 返佣排行
  • 返佣规则
  • 推广学院
实验区
  • Go周边
  • 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

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

赞赏支持

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