数据结构简介:树--------树堆(Treap)

A鱼翔浅底A

381人浏览 · 2020-06-03 17:36:42

A鱼翔浅底A · 2020-06-03 17:36:42 发布

数据结构简介

树堆(Treap)

定义
树堆(Treap)是二叉排序树(Binary Sort Tree)与堆(Heap)结合产生的一种拥有堆性质的二叉排序树.
时间复杂度
期望时间复杂度O(logN)
特点
1)树堆和二叉堆不一样,二叉堆是完全二叉树,且满足堆序性质,但是树堆不一定是完全二叉树.树堆对结构性没有要求
2)树堆满足堆序要求
树堆示例图
树堆旋转
下图中,当X节点优先级小于Y节点时右旋和Y节点优先级小于X节点的左旋,其左右旋转如下图:
树堆示例代码

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模