求分析复杂度
  • 板块学术版
  • 楼主5k_sync_closer
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/5/31 15:31
  • 上次更新2023/10/23 14:14:57
查看原帖
求分析复杂度
388651
5k_sync_closer楼主2023/5/31 15:31

RT,@ZepX_D 发明的一种引入随机化的抽象堆

插入时比较插入值和当前点的大小,

  • 若比当前点大就往随机一个孩子走。
  • 比当前点小就新建一个点 cntcnt 插到当前点和它的父亲之间,把当前点接到 cntcnt 随机一个儿子,然后把当前点的随机一个儿子接到 cntcnt 的另一个儿子。

删除时直接把堆顶与较小的儿子不断交换,到叶节点删除。

本来以为会很难绷,然后过了【模板】堆,求分析期望复杂度。

2023/5/31 15:31
加载中...