Приоритетное дерево поиска может быть построено на множестве точек P за O (n log (n)), но если точки отсортированы по y координатам, тогда это занимает O (n) время.Я нахожу алгоритмы построения дерева, когда точки не отсортированы.
Я придумал способ сделать это следующим образом:
Построить BST по точкам.Поскольку точки отсортированы, это займет O (n) времени
Мин-Heapify BST по x-координатам. Это займет тета (n) время
Таким образом, общая сложность времени будет
O (n) + тета (n) = O (n)
Является ли это правильным подходом для построения приоритетного дерева поиска за время O (n) из набора точек, отсортированных по y-координатам?