Python利用treap實現(xiàn)雙索引的方法
：
在很多應(yīng)用場景下，我們不但需要堆的特性，例如快速知道數(shù)據(jù)最大值或最小值，同時還需要知道元素的排序信息，因此本節(jié)我們看看如何實現(xiàn)魚和熊掌如何兼得。假設(shè)我們有一系列數(shù)據(jù)，它的元素由兩部分組成，一部分對應(yīng)商品的名稱，其類型為字符串，一部分對應(yīng)商品的貨存數(shù)量，類型為整形，我們既需要將商品根據(jù)其名稱排序，同時我們又需要快速查詢當(dāng)前貨存最小的商品，我們?nèi)绾卧O(shè)計相應(yīng)的算法和數(shù)據(jù)結(jié)構(gòu)來滿足這樣特性呢。
舉個例子，如下圖：
從上圖看，它對應(yīng)元素字符串是排序二叉樹，因此根節(jié)點左子樹對應(yīng)元素的字符串都小于根字符串，同時右子樹對應(yīng)的字符串都大于根節(jié)點字符串，同時每個元素還對應(yīng)著相應(yīng)商品的貨存數(shù)量，我們需要及時掌握當(dāng)前貨存最少的商品，這樣才能在其耗盡之前迅速補貨。但是從上圖可以看到，要保證字符串的排序性就得犧牲對于商品數(shù)量的小堆性質(zhì)，例如上圖中water對應(yīng)的貨存與wine對應(yīng)的貨存違背了小堆的性質(zhì)，現(xiàn)在問題是如何在保證字符串排序的情況下，確保數(shù)量同時能滿足小堆性質(zhì)。
首先我們先定義一下數(shù)據(jù)結(jié)構(gòu):
class Node:
def __init__(self, key: str, priority: float):
self._key = key
self._priority = priority
self._left: Node = None
self._right: Node = None
self._parent: Node = None
@property
def left(self):
return self._left
@property
def right(self):
return self._right
@property
def parent(self):
return self._parent
@left.setter
def left(self, node):
self._left = node
if node is not None:
node.parent = self
@right.setter
def right(self, node):
self._right = node
if node is not None:
node.parent = self
@parent.setter
def parent(self, node):
self._parent = node
def is_root(self) -> bool:
if self.parent is None:
return True
return False
def __repr__(self):
return "({}, {})".format(self._key, self._priority)
def __str__(self):
repr_str: str = ""
repr_str += repr(self)
if self.parent is not None:
repr_str += " parent: " + repr(self.parent)
else:
repr_str += " parent: None"
if self.left is not None:
repr_str += " left: " + repr(self.left)
else:
repr_str += " left: None"
if self.right is not None:
repr_str += " right: " + repr(self.right)
else:
repr_str += " right: None"
return repr_str
class Treap:
def __init__(self):
self.root : Node = None
當(dāng)前問題是，當(dāng)上圖所示的矛盾出現(xiàn)時，我們?nèi)绾握{(diào)整，使得字符串依然保持排序性質(zhì)，同時貨存數(shù)值能滿足小堆性質(zhì)。我們需要根據(jù)幾種情況采取不同操作，首先看第一種，如下圖：
從上圖看到，一種情況是父節(jié)點與左孩子在數(shù)值上違背了堆的性質(zhì)，此時我們執(zhí)行一種叫右旋轉(zhuǎn)操作，
其步驟是：
Beer節(jié)點逆時針旋轉(zhuǎn)，替換其父節(jié)點;- 父節(jié)點
Cabbage順時針旋轉(zhuǎn)，成為Beer的右孩子節(jié)點; - 原來
Beer的右孩子節(jié)點轉(zhuǎn)變?yōu)?code>Cabbage的左孩子節(jié)點;
完成后結(jié)果如下圖所示：
可以看到，此時字符串依然保持排序二叉樹性質(zhì)，同時數(shù)值對應(yīng)的小堆性質(zhì)也得到了滿足。
我們看看代碼實現(xiàn)：
class Treap: def __init__(self): self._root: Node = None def right_rotate(self, x: Node): if x is None or x.is_root() is True: return y = x.parent if y.left != x: # 必須是左孩子才能右旋轉(zhuǎn) return p = y.parent if p is not None: # 執(zhí)行右旋轉(zhuǎn) if p.left == y: p.left = x else: p.right = x else: self._root = x y.left = x.right x.right = y
接下來我們構(gòu)造一些數(shù)據(jù)測試一下上面的實現(xiàn)是否正確：
def setup_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 = None
flour.left = cabbage
flour.right = None
cabbage.left = beer
beer.left = bacon
beer.right = butter
return flour, beer
def print_treap(n: Node):
if n is None:
return
print(n)
print_treap(n.left)
print_treap(n.right)
treap = Treap()
root, x , cabbage = setup_right_rotate()
print("---------before right rotate---------:")
print_treap(root)
treap.right_rotate(x)
print("-------after right rotate-------")
print_treap(root)
上面代碼執(zhí)行后輸出內(nèi)容如下：
---------before right rotate---------:
(Flour, 10) parent: None left: (Cabbage, 77) right: None
(Cabbage, 77) parent: (Flour, 10) left: (Beer, 76) right: (Eggs, 129)
(Beer, 76) parent: (Cabbage, 77) left: (Bacon, 95) right: (Butter, 86)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Butter, 86) parent: (Beer, 76) left: None right: None
(Eggs, 129) parent: (Cabbage, 77) left: None right: None
-------after right rotate-------
(Flour, 10) parent: None left: (Beer, 76) right: None
(Beer, 76) parent: (Flour, 10) left: (Bacon, 95) right: (Cabbage, 77)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Cabbage, 77) parent: (Beer, 76) left: (Butter, 86) right: (Eggs, 129)
(Butter, 86) parent: (Cabbage, 77) left: None right: None
(Eggs, 129) parent: (Cabbage, 77) left: None right: None
對比右旋轉(zhuǎn)前后輸出的二叉樹看，旋轉(zhuǎn)后的二叉樹打印信息的確跟上面我們旋轉(zhuǎn)后對應(yīng)的圖像是一致的。接下來我們實現(xiàn)左旋轉(zhuǎn)，先把上圖中cabbage節(jié)點對應(yīng)的值改成75，這樣它與父節(jié)點就違背了小堆性質(zhì)：
我們要做的是：
- 把
cabbage節(jié)點向“左”旋轉(zhuǎn)到beer的位置; beer的父節(jié)點設(shè)置為cabbage;beer的右孩子設(shè)置為cabbage的左孩子;cabbage的左孩子變成beer;左旋轉(zhuǎn)后二叉樹
成形如下：
從上圖看，左旋轉(zhuǎn)后，字符串依然保持二叉樹排序性，同時數(shù)值的排放也遵守小堆原則，我們看相應(yīng)的代碼實現(xiàn)：
class Treap: ... def left_rotate(self, x : Node): if x is None or x.is_root() is True: return y = x.parent if y.right is not x: # 只有右孩子才能左旋轉(zhuǎn) return p = y.parent if p is not None: if p.left is y: p.left = x else: p.right = x else: self._root = x y.right = x.left x.left = y
為了測試上面代碼實現(xiàn)，我們首先把cabbage的值修改，然后調(diào)用上面代碼:
cabbage._priority = 75
print("-------before left rotate--------")
print_treap(root)
treap.left_rotate(cabbage)
print("-------after left rotate---------")
print_treap(root)
代碼運行后輸出結(jié)果為:
-------before left rotate--------
(Flour, 10) parent: None left: (Beer, 76) right: None
(Beer, 76) parent: (Flour, 10) left: (Bacon, 95) right: (Cabbage, 75)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Cabbage, 75) parent: (Beer, 76) left: (Butter, 86) right: (Eggs, 129)
(Butter, 86) parent: (Cabbage, 75) left: None right: None
(Eggs, 129) parent: (Cabbage, 75) left: None right: None
-------after left rotate---------
(Flour, 10) parent: None left: (Cabbage, 75) right: None
(Cabbage, 75) parent: (Flour, 10) left: (Beer, 76) right: (Eggs, 129)
(Beer, 76) parent: (Cabbage, 75) left: (Bacon, 95) right: (Butter, 86)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Butter, 86) parent: (Beer, 76) left: None right: None
(Eggs, 129) parent: (Cabbage, 75) left: None right: None
輸出結(jié)果的描述與上圖左旋轉(zhuǎn)后的結(jié)果是一致的。由于Treap相對于元素的key是排序二叉樹，因此在給定一個字符串后，我們很容易查詢字符串是否在Treap中，其本質(zhì)就是排序二叉樹的搜索，其實現(xiàn)我們暫時忽略。
雖然查詢很簡單，但是插入節(jié)點則稍微麻煩，因為插入后，新節(jié)點與其父節(jié)點可能會違背小堆性質(zhì)，因此在完成插入后，我們還需使用上面實現(xiàn)的左旋轉(zhuǎn)或右旋轉(zhuǎn)來進行調(diào)整。
到此這篇關(guān)于Python使用treap實現(xiàn)雙索引的方法的文章就介紹到這了,更多相關(guān)Python使用treap實現(xiàn)雙索引內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信