data-structures - trep数据结构的用处是什么？

Question

我目前正在研究高级数据结构，我遇到了一种叫做 Treap 的奇怪数据结构。我了解 Treap 是什么，但我似乎无法在有效的用例场景中找到它的实用性。

为什么要使用这样的数据结构以及在什么类型的问题/条件下最好使用陷阱？

我发现自己更喜欢使用哈希映射、最小/最大堆、二叉搜索树或平衡二叉搜索树，但我不知道为什么要使用 treap。

Answer 1

它们更容易实现，更重要的是，如果你想对它们进行细微的改动或以某种方式改变它们，这使得它们更容易在未来进行修改/维护。它们还允许有效的并行版本的集合操作 Union/Intersect/Difference，这是非常有价值的。将它们同时用作堆和二叉树并不是很方便，除非您用于优先级的东西巧合地非常好地随机分布/排列。我想在某些情况下这可能会很方便，但似乎不太可能。如此随机分布的东西通常更像是一个哈希键，通常不能用作有序数据。您希望多久按照 SSN 的顺序将人们拉出？我想这是可能的，但不太可能。