Я думаю, что это невозможно, потому что если это действительно так, люди построят max-heap, а затем используют его для построения BST, что, на мой взгляд, не так.
Пожалуйста, дайте ответ с доказательством.
Нет, вы не можете.
Нижний уровень кучи, который может содержать более половины узлов, может быть полностью неупорядоченным в куче.(представьте, что все внутренние узлы меньше, чем все конечные узлы).
Построение BST определило бы порядок этих узлов, но сортировка занимает время O (n log n), поэтому вы не можете построить BSTв O (N) время.