Repeatedly keep removing 2 smallest elements and add its sum back to the list and return newly inserted elements' total I have a list of unsorted numbers. Each time, I need to remove 2 smallest numbers and insert back its sum into the list. Repeatedly do this till the 1 final element is remaining in the list.

Return the total sum of newly inserted elements

My logic was to use heap sort, remove 2 elems, insert elems sum back - repeat.

This program of input of 10 elements has called heapify function 310 times!

Link: http://cpp.sh/8vkjd

How do I optimize this scenario?


Use Binary Search Tree?
Use Heap Sort on LinkedList?
Is this possible with graphs?
Since there are several insertions, I'm trying to only restrict to O(N) or \$O(\log N)\$ or \$O(n \log N)\$ insertion.
Can this be done with 2 lists?
Since the elements will be sorted after the 1st iteration, is there a good insertion algorithm that does faster insertion?




#include &lt;iostream&gt;
#include &lt;sstream&gt;
#include &lt;vector&gt;
int count = 0; // A global variable to keep track of number of time heapify function is called
void heapify(std::vector&lt;int&gt; &amp;arr, int n, int i)
{
   count++;
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if(l&lt;n &amp;&amp; arr[l] &gt;arr[largest])
       largest = l;

   if(r&lt;n &amp;&amp; arr[r] &gt; arr[largest])
       largest = r;

   if(largest != i)
   {
       std::swap(arr[i], arr[largest]);
       heapify(arr, n, largest);
   }
}

void heapSort(std::vector&lt;int&gt; &amp;arr, int n)
{
   for(int i=n/2 -1 ; i&gt;=0 ; i--)
   {
       heapify(arr,n,i);
   }


   for(int i=n-1 ; i&gt;=0 ; i--)
   {
       std::swap(arr[0],arr[i]);
       heapify(arr,i,0);
   }

}

void printArray(std::vector&lt;int&gt; &amp;arr, int n)
{
   for(int i=0 ; i&lt;n ; i++)
   {
       std::cout &lt;&lt; arr[i] &lt;&lt; " ";
   }
   std::cout &lt;&lt; std::endl;
}

int main()
{
   std::vector&lt;int&gt; arr{1,2,3,4,5,6,7,8,9,10};
   int n = arr.size();
   printArray(arr,n);
   heapSort(arr,n);

   int ans=0;
   int tempEle=0;
   while(arr.size()&gt;1)
   {
       heapSort(arr,n);
       tempEle = arr[0]+arr[1];
       arr.erase(arr.begin(),arr.begin()+2);
       ans+=tempEle;
       arr.push_back(tempEle);
       printArray(arr,arr.size());
   }
   ans+=arr[0];

   std::cout &lt;&lt; "Repeatedly adding all elements, 2 small elements at a time and reducing it to a single number : " &lt;&lt; ans &lt;&lt; std::endl;

   std::cout &lt;&lt; "Heapify was called " &lt;&lt; count &lt;&lt; " times" &lt;&lt; std::endl;
   return 0;
}




And for an input of 5000 numbers, the heapify() func is being called 246 million times.
#include &lt;sstream&gt;


Only include what is necessary.



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


Use range-based for.

    std::cout &lt;&lt; ... &lt;&lt; std::endl;


Avoid std::endl.



void printArray(std::vector&lt;int&gt; &amp;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() &gt; 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 &lt;algorithm&gt;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() &gt; 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() &gt; 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);
    }