Извлечение 2 чисел n раз и добавление обратно за O(n) вместо O(n*log(n))

Я представляю задачу, которую мой профессор показал в классе, с моим решением O(n*log(n)):

Дан список из nчисел, которые нам нужны выполнить следующие n-1раз:

• Извлечь два минимальных элемента x,yиз списка и представить их
• Создать новое число z, где z = x+y
• Поместить zобратно в список

Предложить структуру данных и алгоритм для O(n*log(n))и O(n)

Решение:

Мы будем использовать минимальную кучу:

Однократное создание кучи займет O(n). После этого извлечение двух минимальных элементов займет O (log (n)). Помещение zв кучу потребует O(log(n)).

Выполнение описанного выше n-1раз потребует O(n*log(n)), поскольку:

O(n)+O(n∙(logn+logn ))=O(n)+O(n∙logn )=O(n∙logn )

Но как я могу сделать это за O(n)?

РЕДАКТИРОВАТЬ:

Говоря: «извлеките два минимальных элемента x, yиз списка и представьте их », я имею в виду printf("%d ,%d" , x,y), где xи y— наименьшие элементы в текущем списке.