5
\$\begingroup\$

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

sample test case for 10 elements showing expected output

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Seems like busy work; you could simply add all the integers together in unsorted order, O(N) time and O(1) space, and the result would be the same. If the unsorted array contained floating point numbers, the approach of adding together the smallest numbers first can improve the accuracy of the resulting sum; with fixed point numbers (including integers), this is pointless. \$\endgroup\$ – AJNeufeld Apr 7 at 21:36
  • \$\begingroup\$ @AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum. \$\endgroup\$ – Manjunath Apr 7 at 22:39
  • 1
    \$\begingroup\$ If you have 10 numbers, how many additions will be performed? \$\endgroup\$ – E.Coms Apr 8 at 0:15
  • \$\begingroup\$ @E.Coms: For 10 elements, there are 10 add operations will be performed and 10 insertion operations will be performed and 10*2=20 remove operations will be performed on that list \$\endgroup\$ – Manjunath Apr 8 at 2:22
  • 1
    \$\begingroup\$ Use a heap to keep the list sorted. \$\endgroup\$ – Martin York Apr 8 at 8:35
2
\$\begingroup\$
#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);
    }
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ this code is so good. thank you. Looks like this will perform better than a Balanced BST too. \$\endgroup\$ – Manjunath Apr 8 at 17:17
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.