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 <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.