Слияние двух кучек: O (n * log (n)) по сравнению с O (n + m)

Question

Я хочу объединить двоичную кучу, реализованную как массив с размером m в другую кучу (одного и того же типа) с n элементами , Используя повторяющиеся вставки, это принимает O (m * log (n)). Представляется общепринятым, что альтернативный метод конкатенации массивов, а затем перестройка кучи, принимая O (m + n), более эффективен.

Теперь мне кажется, что для некоторых пар (m, n) с m < n метод O (m * log (n)) будет более эффективным. According to Wolfram Alpha это относится к m < (n * log (2))/log (n/2). Правильно ли это толкование? И стоит ли проверить эффективность выполнения/время выполнения?

Answer 1

Ваше сообщение неверно. Когда вы вставляете элементы один за другим в первую кучу, размер его увеличивается, приближаясь к m+n, поэтому сложность каждой вставки больше не будет O (log (n)). Фактически вставка элементов по одному будет иметь сложность порядка O(m * log(m + n)).

Это делает ограничение для значения m, для которого лучше вставлять значения из меньшей кучи один за другим, но не устраняет его. Например, если у вас есть куча размером 100000 и вы хотите объединить ее с кучей размера 2, лучше вставить два элемента.

Также обратите внимание, что существуют разные типы кучи, которые поддерживают операцию слияния с лучшей сложностью. Например, leftist heap прост в реализации и поддерживает слияние в O(log(n)).