Изменения

Отсортируем все приоритеты по убыванию за <tex> O(n\log n) </tex> и выберем первый из них, пусть это будет <tex>y_k</tex>. Сделаем <tex>(x_k, y_k)</tex> корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына <tex>(x_k, y_k)</tex>. В среднем высота Декартова дерева <tex>\log n</tex> (см. далее) и на каждом уровне мы сделали <tex>O(\log n)</tex> операций. Значит такой алгоритм работает за <tex>O(n\log n)</tex>.