Предполагая, что у вас есть доступ к вспомогательному массиву, который содержит двоичную кучу, и вы можете перебирать его за O (n) время, тогда вы можете создать свою биномиальную кучу, просто выполнив n вставок.Как говорится в статье Википедии :
Вставить новый элемент в кучу можно, просто создав новую кучу, содержащую только этот элемент, а затем объединив ее с исходной кучей.Из-за слияния вставка занимает O (log n) времени.Однако в серии из n последовательных вставок время вставки имеет амортизированное время O (1) (т. Е. Постоянное).
Другими словами, выполнение n вставок в биномиальную кучу потребует O (n) время.
Вы не можете сделать это за O (n) время с помощью стандартной операции удаления двоичной кучи.Как вы заметили, это будет O (log n) для каждого удаления, что приведет к сложности O (n log n).