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

Question

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?

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

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

   if(l<n && arr[l] >arr[largest])
       largest = l;

   if(r<n && arr[r] > arr[largest])
       largest = r;

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

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


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

}

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

int main()
{
   std::vector<int> 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()>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 << "Repeatedly adding all elements, 2 small elements at a time and reducing it to a single number : " << ans << std::endl;

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

And for an input of 5000 numbers, the heapify() func is being called 246 million times.

Answer 1

#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);
    }

Answer 2

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;
}

Answer 3

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.