Сначала отметим, что мы можем - без ограничения общности - предположить, что в нашем двоичном дереве есть элементы 1,2,3, ... 2^m-1. Итак, теперь мы предполагаем, что у нас есть эти числа.
Затем я попытался бы преобразовать отсортированный массив (т.е. 1 2 3 4 5) в массив, представляющий отсортированное двоичное дерево.
В отсортированном двоичном дереве с (2^m)-1 элементами мы всегда имеем, что «основание» дерева состоит из всех неравных чисел, например, для m=3:
4
2 6
1 3 5 7
Это означает, что в соответствующем массиве мы имеем, что последние числа - это все неравные числа:
4 2 6 1 3 5 7
-------
^
uneven numbers!
Таким образом, мы можем построить последнюю «строку» двоичного дерева, убедившись, что последние 2^(m-1) числа в соответствующем массиве - это все нечетные числа. Поэтому все, что нам нужно сделать для последней строки, - это создать функцию, которая перемещает все элементы в позиции с неравными индексами в последнюю строку.
Итак, давайте пока предположим, что у нас есть подпрограмма, которая - учитывая отсортированный массив в качестве входных данных - правильно устанавливает последнюю строку.
Затем мы можем вызвать подпрограмму для всего массива, чтобы построить последнюю строку, в то время как все остальные элементы остаются отсортированными. Когда мы применяем эту процедуру к массиву 1 2 3 4 5 6 7, мы имеем следующую ситуацию:
2 4 6 1 3 5 7
-------
^
correct!
После первого раунда мы применяем подпрограмму для оставшегося подмассива (а именно 2 4 6), которая создает вторую последнюю «строку» нашего двоичного дерева, в то время как мы оставляем оставшиеся элементы без изменений, поэтому получаем следующее:
now correct as well!
v
---
4 2 6 1 3 5 7
-------
^
correct from run before
Итак, все, что нам нужно сделать, - это построить функцию, которая правильно устанавливает последнюю строку (т.е. вторую половину массива)!
Это можно сделать в O(n log n), где n - входной размер массива. Поэтому мы просто пересекаем массив от конца к началу и меняем неровные позиции таким образом, чтобы последняя строка (то есть вторая половина массива) была правильной. Это можно сделать на месте. После этого мы сортируем первую половину массива (например, с помощью heapsort). Таким образом, все время выполнения этой подпрограммы составляет O(n log n).
Таким образом, время выполнения для массива размером n в общей сложности:
O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ..., что совпадает с O(n log n). Обратите внимание, что мы должны использовать алгоритм сортировки на месте, такой как Heapsort, чтобы весь этот материал работал полностью на месте.
Мне жаль, что я не могу уточнить это дальше, но я думаю, что вы можете понять идею.