Repeatedly keep removing 2 smallest elements and add its sum back to the list and return newly inserted elements' total

#include <sstream> 

Only include what is necessary.

 for(int i=0 ; i<n ; i++) { ... } 

Use range-based for.

 std::cout << ... << std::endl; 

Avoid std::endl.

void printArray(std::vector<int> &arr, int n) { ... } ^^^^^ int main() { int n = arr.size(); ^^^^^^^^^^^^ printArray(arr,n); ^ 

You have an implicit conversions from std::vector::size_type to int when you initialize n and pass an int argument to parameter n.

 printArray(arr, n); heapSort(arr, n); 

std::vector carries its size. You do not have to capture it in a variable and pass it.

 int n = arr.size(); while (arr.size() > 1) { heapSort(arr, n); arr.erase(...); arr.push_back(...); } 

With each iteration of the loop, you pop 2 elements and push 1 element reducing the size of arr by 1. n is a local copy of arr.size() and is never updated. This results in out-of-bounds index access in your sort functions after the first iteration of this loop.

As for your issues with excessive calls to heapify(), you are calling heapSort() on every iteration. heapSort() takes a sequence in any order, sorts all of the values into heap order, then sorts all of the values again into sequential sorted order. This is done so you can operate on the two minimum values at the same time. Instead of fully sorting the sequence on every iteration, you can take a partial sort approach. Maintain the sequence in heap order by sifting values around as you mutate the sequence. Finding each minimum values is simply a swap and a sift down. Repairing the heap order on insertion is simply a sift up. Which brings me to know your <algorithm>s. The C++ standard library provides heap operations (is, make, push, pop, sort).

 // Sort into min-heap order std::make_heap(arr.begin(), arr.end(), std::greater()) while (arr.size() > 1) { // rotate out the 1st min keeping heap order intact std::pop_heap(arr.begin(), arr.end(), std::greater()); const auto first = arr.back(); arr.pop_back(); // rotate out the 2nd min keeping heap order intact std::pop_heap(arr.begin(), arr.end(), std::greater()); const auto second = arr.back(); arr.pop_back(); const auto sum = first + second; ans += sum; // Move the inserted value into its heap order position arr.push_back(sum); std::push_heap(arr.begin(), arr.end(), std::greater()); } 

std::priority_queue helps clean up some of the duplication.

 std::priority_queue min_heap{std::greater(), std::move(arr)}; while (min_heap.size() > 1) { const auto first = min_heap.top(); min_heap.pop(); const auto second = min_heap.top(); min_heap.pop(); const auto sum = first + second; ans += sum; min_heap.push(sum); } 

There is a cleaner way to write your algorithm, relying on iterators and <algorithm>. Cleaner is almost always better, because you can more easily reason about your code and spot the bugs' origin. Let me ask you a few questions:

• what are those i and n variables? (there's a good chance you'll have to look back at your code, and maybe match your code and what you know / remember about the algorithm you used; whereas first, last are always iterators to the first and past the last elements, no need to check). By the way n isn't even used.

• how will your functions react if given an empty vector? If i isn't coherent with the vector's size? (idem, you'll need to check, think about the division result, etc).

• what will your function return if given an empty vector? 0 seems a good choice, but in some contexts, the absence of elements should be discriminated from the presence of null values. With iterators, last is the default "void" or "failure" value.

• the requirements are also clearly stated in the <algorithm> implementation: for instance, std::nth_element could be used here but requires iterators to be random access iterators. You won't use it on a linked list. On the other hand, std::min_element only requires forward iterators, so is compatible with a linked list. Having the least two elements at the beginning would look like

this:

std::iter_swap(first, std::min_element(first, last)); std::iter_swap(std::next(first), std::min_element(std::next(first), last)); 

So here's for instance what I'd consider a cleaner code:

template <typename Iterator> auto bottom_progressive_sum(Iterator first, Iterator last) { if (first == last) return last; if (std::next(first) == last) return first; while (std::next(first) != last) { std::iter_swap(first, std::min_element(first, last)); std::iter_swap(std::next(first), std::min_element(std::next(first), last)); *std::next(first) += *first; ++first; } *std::next(first) += *first; return ++first; } 

The numbers you insert must be monotonic increasing (either strictly larger than the last or equal to it).

So: sort the original list smallest to largest.

Create a second, empty queue.

Peek at four values: the head and next of the sorted list, and the head and next of the queue. Remove the lowest two, and push their sum onto the queue.

Of course, you could also just sum the list in O(n) time, but exploiting the fact that the sums are monotonic increasing allows you to avoid a bunch of heapifys. Repeat until both the list and queue are empty.