Здравствуйте, subdmitry, Вы писали:

S>Количество слияний куч никак не влияет на эту оценку.

Конечно, сливаемые кучи придумали от того, что заняться нечем было.

S>Так как каждую из этих сливаемых куч надо для начала создать, а это O(n log n).
И что теперь? Сливать-то кучу можно с остальными многократно.

Простейший пример: имели n куч по одному элементу. Затем итеративно берем первую и вторую кучу из списка, сливаем и снова ставим в начало. Если куча meldable, то оценка будет O(n log n), а если нет -- то квадратичная.