Задача «Декартово дерево»

Произвести рефакторинг модуля, реализующего декартово дерево (treap = tree + heap = дерамида).

В процессе рефакторинга необходимо:

Переписать код на C++ (new, delete, объявление переменных не в начале блока, а там где они реально используются, и т. п.)
Текстовый ввод и вывод производить через std::cout и т.п
Избавиться от define'ов (объявление констант) и глобальных переменных.
Уйти от работы с указателями в пользу ссылок, где это возможно.
Вместо typedef int ElementType использовать шаблоны.
Предусмотреть возможность передачи в качестве параметра шаблона нетривиальных типов данных (потребуется передача функционального объекта, аналогичного std::less).
Избавиться от typedef struct TreapNode *Position создав итератор.
Обработку ошибок перенести на механизм исключений и std::exception.
Выделить класс дерамиды, глобальные функции для работы с дерамидой преобразовать в методы.
Выделить класс узла дерева – оформить как внутренний класс дерамиды.

В целом, получившийся класс должен приближаться к интерфейсу std::set по мере возможностей (принципиально новый функционал дописывать не нужно).