Python高级算法与数据结构:使用treap实现双索引之一

来源:陈屹 Coding迪斯尼 日期:2021-09-15

\

前面介绍的堆结构只能对数据进行部分排序,也就是它只能知道部分元素的排序,例如从根节点出发,沿着左孩子或右孩子前行,我们能得知所遍历的元素一定是递增(小堆)或是递减(大堆)关系,但是我们无法得知左子树与右子树两部分节点的排序关系。

在很多应用场景下,我们不但需要堆的特性,例如快速知道数据最大值或最小值,同时还需要知道元素的排序信息,因此本节我们看看如何实现鱼和熊掌如何兼得。假设我们有一系列数据,它的元素由两部分组成,一部分对应商品的名称,其类型为字符串,一部分对应商品的货存数量,类型为整形,我们既需要将商品根据其名称排序,同时我们又需要快速查询当前货存最小的商品,我们如何设计相应的算法和数据结构来满足这样特性呢。

举个例子,如下图:

从上图看,它对应元素字符串是排序二叉树,因此根节点左子树对应元素的字符串都小于根字符串,同时右子树对应的字符串都大于根节点字符串,同时每个元素还对应着相应商品的货存数量,我们需要及时掌握当前货存最少的商品,这样才能在其耗尽之前迅速补货。但是从上图可以看到,要保证字符串的排序性就得牺牲对于商品数量的小堆性质,例如上图中water对应的货存与wine对应的货存违背了小堆的性质,现在问题是如何在保证字符串排序的情况下,确保数量同时能满足小堆性质。

首先我们先定义一下数据结构:

  1. class Node: 
  2.     def __init__(self, key: str, priority: float): 
  3.         self._key = key 
  4.         self._priority = priority 
  5.         self._left: Node = None 
  6.         self._right: Node = None 
  7.         self._parent: Node = None 
  8.  
  9.     @property 
  10.     def left(self): 
  11.         return self._left 
  12.  
  13.     @property 
  14.     def right(self): 
  15.         return self._right 
  16.  
  17.     @property 
  18.     def parent(self): 
  19.         return self._parent 
  20.  
  21.     @left.setter 
  22.     def left(self, node): 
  23.         self._left = node 
  24.         if node is not None: 
  25.             node.parent = self 
  26.  
  27.     @right.setter 
  28.     def right(self, node): 
  29.         self._right = node 
  30.         if node is not None: 
  31.             node.parent = self 
  32.  
  33.     @parent.setter 
  34.     def parent(self, node): 
 1/6    1 2 3 4 5 下一页 尾页
    A+
声明:本文转载自其它媒体,转载目的在于传递更多信息,并不代表赞同其观点和对其真实性负责。