博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
左偏树初识到应用
阅读量:5360 次
发布时间:2019-06-15

本文共 658 字,大约阅读时间需要 2 分钟。

前言

堆与可删除堆已经是烂大街的数据结构了,毒瘤的出题人从而考虑从左偏树下手,也就是俗称的可合并堆

性质

我们新定义一个节点的距离为到最近叶子节点的距离

\(1、\)左儿子距离\(≥\)右儿子,左偏就是这个意思
\(2、\)节点距离等于右儿子距离\(+1\)(显然)
\(3、\)节点距离是\(log\)级别的(显然)

前置

堆本质是维护一个集合里特定值,既然是个集合,并查集查询位置是必不可少的(压缩)

合并

左偏树唯一的好处就是能快速合并,而既然距离是\(log\)级别的,所以合并自然要利用右儿子/距离

流程:不断确定当前根,右儿子递归下去合并,非满集时继承

LL Merge(LL x,LL y){    if(!x || !y) return x+y;    if(val[x]>val[y] || (val[x]==val[y] && y

删除

删除的标志是值为\(-1\)

最后一句有点奇怪:压缩路径后原本指向\(x\)的位置我们需要通过已删除点作为媒介(最后的用途)指向新集标号

inline void pop(LL x){    val[x]=-1;    f[son[x][0]]=son[x][0];    f[son[x][1]]=son[x][1];    f[x]=merge(son[x][0],son[x][1]);}

应用

维护总和,总和超过限制弹出堆顶,不断往上合并

转载于:https://www.cnblogs.com/y2823774827y/p/10570704.html

你可能感兴趣的文章
Linux常用命令(十四)
查看>>
Linux常用命令(十七)
查看>>
Linux常用命令(十六)
查看>>
Linux常用命令(二十四)
查看>>
4种java定时器
查看>>
Vue.js 教程
查看>>
linux 设置网卡
查看>>
hive 语法 case when 语法
查看>>
Ajax:js读取txt内容(json格式内容)
查看>>
Task 7 买书最低价格问题
查看>>
Selenium3+python自动化007-警告框
查看>>
html5 相同形状的图形进行循环
查看>>
springboot中文官方文档
查看>>
ThreadLocal实现线程范围内共享
查看>>
多校HDU5723 最小生成树+dfs回溯
查看>>
ASP.NET MVC分页实现之改进版-增加同一个视图可设置多个分页
查看>>
关于ASP.NET MVC开发设计中出现的问题与解决方案汇总 【持续更新】
查看>>
关于Entity Framework中的Attached报错的完美解决方案终极版
查看>>
Selenium之Web页面滚动条滚操作
查看>>
组合数据类型练习,英文词频统计实例上
查看>>