\前面介绍的堆结构只能对数据进行部分排序，即只能知道部分元素的排序，比如从根节点，沿着左孩子或者右孩子向前移动的时候，我们可以知道遍历的元素一定是递增（小堆）或者递减（大堆）的关系，但是我们无法知道它们之间的顺序关系左子树和右子树两部分。在很多应用场景中，我们不仅需要堆的特性，比如快速知道数据的最大值或者最小值，还需要知道元素的排序信息，那么本节我们就来看看如何实现两个都。假设我们有一系列数据，它的元素由两部分组成，一部分对应商品的名称，类型为字符串，另一部分对应商品的库存数量，类型为整数。我们需要将商品按照名称进行排序，同时我们也需要快速查询当前库存最小的商品。我们如何设计相应的算法和数据结构来满足这样的特点。例如，如下图所示：从上图可以看出，它对应的元素串是一棵排序好的二叉树，所以根节点的左子树中的元素对应的串都小于根串，则右子树对应的字符串大于根节点，同时每个元素也对应对应产品的库存数量。我们需要及时知道库存最少的产品，以便在它用完之前快速补货。但是从上图可以看出，要保证字符串的有序性，必须牺牲小堆货的性质。比如上图中水对应的存货和酒对应的存货就违背了小堆的性质。现在的问题是如何在保证字符串排序的同时，保证数字能够满足小堆的性质。首先我们首先确定下数据结构:classNode:def__init__(self,key:str,priority:float):self._key=keyself._priority=priorityself._left:Node=Noneself._right:Node=Noneself._parent:Node=None@propertydefleft(self):returnsself._left@propertydefright(self):returnsself._right@propertydefparent(self):returnsself._parent@left.setterdefleft(self,node):self._left=nodeifnodeisnotNone:node.parent=self@right.setterdefright(self,node):self._right=nodeifnodeisnotNone:node.parent=self@parent.setterdefparent(self,node):self._parent=nodedefis_root(self)->bool:ifself.parentisNone:returnTruereturnFalsedef__repr__(self):return"({},{})".format(self._key,self._priority)def__str__(self):repr_str:str=""repr_str+=repr(self)ifself.parentisnotNone:repr_str+="parent:"+repr(self.parent)else:repr_str+="parent:None"ifself.leftisnotNone:repr_str+="left:"+repr(self.left)else:repr_str+="left:None"ifself.rightisnotNone:repr_str+="right:"+repr(self.right)else:repr_str+="right:None"returnrepr_strclassTreap:def__init__(self):self.root:Node=None目前的问题是，当出现上图所示的矛盾时，我们该如何调整使得字符串仍然保持排序属性，同时库存值可以满足小堆属性。我们需要根据几种情况采取不同的操作。首先看第一种，如下图所示：从上图可以看出，一种情况是父节点和左子节点的值违反了堆的性质。这时候，我们进行一次右旋操作。步骤为：1.Beer节点逆时针旋转，替换其父节点；2、父节点Cabbage顺时针旋转成为BeerChild节点的右节点；3、原先的Beer右子节点转化为Cabbage的左子节点；完成后的结果如下图所示：可以看出此时字符串仍然保持了排序二叉树的性质，值对应的小堆的性质也得到了满足。下面看代码实现：classTreap:def__init__(self):self._root:Node=Nonedefright_rotate(self,x:Node):ifxisNoneorx.is_root()isTrue:returny=x.parentify.left!=x:#mustbeleft孩子可以向右旋转returnp=y.parentifpisnotNone:#执行向右旋转ifp.left==y:p.left=xelse:p.right=xelse:self._root=xy.left=x.rightx.right=yNext让我们构造一些数据来测试上面的实现是否正确：defsetup_right_rotate():flour:Node=Node("Flour",10)cabbage:Node=Node("Cabbage",77)beer:Node=Node("Beer",76)bacon:Node=Node("Bacon",95)butter:Node=Node("Butter",86)flour.parent=Noneflour.left=cabbageflour.right=Nonecabbage.left=beerbeer.left=baconbeer.right=butterreturnflour,beerdefprint_treap(n:Node):ifnisNone:returnprint(n)print_treap(n.left)print_treap(n.right)treap=Treap()root,x,cabbage=setup_right_rotate()打印("---------beforerightrotate----------:")print_treap(root)treap.right_rotate(x)print("--------afterrightrotate--------")print_treap(root)上面代码执行后输出结果如下：----------beforerightrotate---------:(Flour,10)parent:Noneleft:(Cabbage,77)right:None(Cabbage,77)parent:(Flour,10)left:(Beer,76)right:(Eggs,129)(Beer,76)parent:(卷心菜,77)left:(Bacon,95)right:(Butter,86)(Bacon,95)parent:(Beer,76)left:Noneright:None(Butter,86)parent:(Beer,76)left:Noneright:None(Eggs,129)parent:(Cabbage,77)left:Noneright:None-------afterrightrotate-------(Flour,10)parent:Noneleft:(Beer,76)right:None(Beer,76)parent:(Flour,10)left:(Bacon,95)right:(Cabbage,77)(Bacon,95)parent:(Beer,76)left:Noneright:None(卷心菜,77）父母：（啤酒，76）左：（黄油，86）右：（鸡蛋，129）（黄油，86）父母：（卷心菜，77）左：无右：无（鸡蛋，129）父母：（卷心菜,77)left:Noneright:None比较右旋前后二叉树输出，旋转后的二叉树打印信息确实和我们上面旋转后对应的图像一致接下来我们实现左旋转，首先将上图中的白菜节点对应的值改为75，这样它和父节点就违反了小堆的性质：我们需要做的是：1、将白菜节点旋转到“左边”啤酒的位置；2、beer的父节点设置为cabbage；3：啤酒的右孩子设置为白菜的左孩子；4、白菜剩下的孩子变成啤酒；左旋后二叉树的形状应该是这样的：从上图来看，左旋后字符串仍然保持二叉树的排序属性，值的排出也遵循小堆原则。下面看对应的代码实现：classTreap:...defleft_rotate(self,x:Node):ifxisNoneorx.is_root()isTrue:returny=x.parentify.rightisnotx:#只有右孩子可以向左旋转returnp=y.parentifpisnotNone:ifp.leftisy:p.left=xelse:p.right=xelse:self._root=xy.right=x.leftx.left=y为了测试上面代码的实现，我们先修改cabbage，然后调用上面的代码：cabbage._priority=75print("--------beforeleftrotate--------")print_treap(root)treap.left_rotate(cabbage)print("-------afterleftrotate--------")print_treap(root)代码运行后的输出为：------beforeleftrotate--------(Flour,10)parent:Noneleft:(Beer,76)right:None(Beer,76)parent:(Flour,10)left:(Bacon,95)right:(Cabbage,75)(Bacon,95)parent:(Beer,76)左：无右：无（卷心菜，75）父：（啤酒，76）左：（黄油，86）右：（鸡蛋，129）（黄油，86）父：（卷心菜，75）左：无右：无（鸡蛋,129)parent:(卷心菜,75)left:Noneright:None------afterlefrotate---------(Flour,10)parent:Noneleft:(卷心菜,75)right:None(卷心菜,75)父母:(面粉,10)左:(啤酒,76)右:(鸡蛋,129)(啤酒,76)父母:(卷心菜,75)左:(培根,95)右:(黄油,86）（培根，95）父母：（啤酒，76）左：无右：无（黄油，86）父母：（啤酒，76）左：无右：无（鸡蛋，129）父母：（卷心菜，75）左：Noneright:None输出结果的描述与上图中左旋的结果一致。由于Treap相对于元素的key是一棵排序好的二叉树，给定一个字符串后，我们可以很方便的查询到该字符串是否在Treap中。本质就是对二叉树的查找进行排序，我们暂时忽略它的实现。查询虽然简单，但是插入节点有点麻烦，因为插入后，新节点及其父节点可能会违反小堆属性，所以插入完成后，我们需要使用上面实现的左旋或右旋调整。
