堆简介


堆是一棵树,其每个节点都有一个键值,且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆,否则叫做大根堆。

STL 中的 priority_queue 其实就是一个大根堆。

(小根)堆主要支持的操作有:插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

一些功能强大的堆(可并堆)还能(高效地)支持 merge 等操作。

一些功能更强大的堆还支持可持久化,也就是对任意历史版本进行查询或者操作,产生新的版本。

堆的分类

操作\数据结构配对堆二叉堆左偏树二项堆斐波那契堆
插入(insert)
查询最小值(find-min)
删除最小值(delete-min)
合并 (merge)
减小一个元素的值 (decrease-key)(下界 ,上界 )
是否支持可持久化

习惯上,不加限定提到“堆”时往往都指二叉堆。

贡献者:@CCXXXI@Early@mgt@Margatroid@CyaceQuious@Ir1d@Heran@sshwy@WAAutoMaton

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组