Описание тега treap
Treap - это форма структуры данных двоичного дерева поиска, которая поддерживает динамический набор упорядоченных ключей и позволяет выполнять двоичный поиск среди ключей.
Treap (дерево + куча) - это декартово дерево, в котором каждому ключу дается (случайно выбранный) числовой приоритет. Как и в случае любого двоичного дерева поиска, порядок обхода узлов такой же, как отсортированный порядок ключей.
Структура дерева определяется требованием, чтобы оно было упорядочено в куче: то есть номер приоритета для любого нелистового узла должен быть больше или равен приоритету его дочерних узлов.
Таким образом, как и в случае с декартовыми деревьями в более общем смысле, корневой узел является узлом с максимальным приоритетом, и его левое и правое поддеревья формируются таким же образом из подпоследовательностей отсортированного порядка слева и справа от этого узла.