Объединить две кучи деревьев в log (n + m)

Question

Как объединить две кучи деревьев (тип деревьев не определен), когда размер одного равен n, а другого - m в O (log (п + т))?

Answer 1

Вопрос действительно абсурд. Даже копирование одной кучи в новое дерево кучи потребляет время O (N log N). Как вы можете объединить два таких дерева только с временной сложностью журнала (N). Даже в лучшем случае, когда две кучи идентичны, время, необходимое для копирования узлов в новое дерево кучи, принимает O (N) время по крайней мере.