Vwwxrf

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.

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 with 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 <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> arr1,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;