一個平衡的二叉搜索樹，這也是堆

Question

我正在尋找一個數據結構，其中的每個元素都有兩個鍵。其中之一的結構是BST，看着另一個，數據結構是一堆。通過一些搜索，我找到了一個名爲Treap的結構。它使用heap屬性和堆密鑰上的隨機分佈來使BST平衡！

我想要的是一個平衡BST，它也可以是一堆。如果我按照我選擇的順序插入堆密鑰元素，Treap中的BST可能不平衡。

有沒有這樣的數據結構？

Answer 1

優先搜索樹是既是平衡BST又是堆的結構。詳情請參閱this paper或本書："Handbook of Data Structures and Applications"（第18.5章）。

該結構可以用於有效地搜索在給定範圍內具有最小「堆」鍵和「BST」鍵的元素。