В чем полезность структуры данных Treap?
В настоящее время я изучаю сложные структуры данных и натолкнулся на странную структуру данных под названием Treap. Я понимаю, что такое Treap, но не могу найти его полезным в сценарии правильного использования.
Почему вы должны использовать такую структуру данных и в каких типах проблем / условий лучше всего использовать трепы?
Я гораздо больше увлекаюсь использованием хеш-карт, мин / макс кучи, бинарного дерева поиска или сбалансированных бинарных деревьев поиска, но я не могу сказать, почему вы должны использовать трейп.
1 ответ
Их легче реализовать и, что более важно, это облегчает их модификацию / сопровождение в будущем, если вы хотите внести в них небольшие изменения или изменить их каким-либо образом. Они также позволяют создавать эффективные параллельные версии операций над множествами Union/Intersect/Difference, что чрезвычайно ценно. Использование их одновременно в качестве кучи и двоичного дерева на самом деле не очень удобно, если только материал, который вы используете для приоритетов, случайно не случайно распределен / переставлен случайным образом. Я предполагаю, что может быть случай, когда это будет удобно, но это кажется маловероятным. Распределение данных по случайному принципу обычно больше похоже на хэш-ключ, который обычно не используется в качестве упорядоченных данных. Как часто вы хотите выводить людей в порядке их SSN? Я думаю, что это возможно, но вряд ли.