Repeatedly keep removing 2 smallest elements and add its sum back to the list
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
3
$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?
- 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.
c++ algorithm sorting tree heap
edited 59 secs ago
Jamal♦
30.6k11121227
asked 6 hours ago
ManjunathManjunath
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
3
$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?
- 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.
c++ algorithm sorting tree heap
edited 59 secs ago
Jamal♦
30.6k11121227
asked 6 hours ago
ManjunathManjunath
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$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
5 hours ago
$begingroup$
@AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum.
$endgroup$
– Manjunath
4 hours ago
$begingroup$
If you have 10 numbers, how many additions will be performed?
$endgroup$
– E.Coms
2 hours ago
$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
40 mins ago
add a comment |
3
3
3
$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?
- 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.
c++ algorithm sorting tree heap
edited 59 secs ago
Jamal♦
30.6k11121227
asked 6 hours ago
ManjunathManjunath
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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.
c++ algorithm sorting tree heap
c++ algorithm sorting tree heap
edited 59 secs ago
Jamal♦
30.6k11121227
asked 6 hours ago
ManjunathManjunath
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 59 secs ago
Jamal♦
30.6k11121227
asked 6 hours ago
ManjunathManjunath
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 59 secs ago
Jamal♦
30.6k11121227
edited 59 secs ago
Jamal♦
30.6k11121227
edited 59 secs ago
Jamal♦
30.6k11121227
30.6k11121227
asked 6 hours ago
ManjunathManjunath
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 6 hours ago
ManjunathManjunath
164
asked 6 hours ago
ManjunathManjunath
164
164
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Manjunath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
5 hours ago
$begingroup$
@AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum.
$endgroup$
– Manjunath
4 hours ago
$begingroup$
If you have 10 numbers, how many additions will be performed?
$endgroup$
– E.Coms
2 hours ago
$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
40 mins ago
add a comment |
$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
5 hours ago
$begingroup$
@AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum.
$endgroup$
– Manjunath
4 hours ago
$begingroup$
If you have 10 numbers, how many additions will be performed?
$endgroup$
– E.Coms
2 hours ago
$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
40 mins ago
$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
5 hours ago
$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
5 hours ago
$begingroup$
@AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum.
$endgroup$
– Manjunath
4 hours ago
$begingroup$
@AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum.
$endgroup$
– Manjunath
4 hours ago
$begingroup$
If you have 10 numbers, how many additions will be performed?
$endgroup$
– E.Coms
2 hours ago
$begingroup$
If you have 10 numbers, how many additions will be performed?
$endgroup$
– E.Coms
2 hours ago
$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
40 mins ago
$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
40 mins ago
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Manjunath is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217034%2frepeatedly-keep-removing-2-smallest-elements-and-add-its-sum-back-to-the-list%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Manjunath is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Manjunath is a new contributor. Be nice, and check out our Code of Conduct.
Manjunath is a new contributor. Be nice, and check out our Code of Conduct.
Manjunath is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217034%2frepeatedly-keep-removing-2-smallest-elements-and-add-its-sum-back-to-the-list%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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
5 hours ago
$begingroup$
@AJNeufeld: condition is to remove the minimum 2 elements in a list every single time and add it to the sum.
$endgroup$
– Manjunath
4 hours ago
$begingroup$
If you have 10 numbers, how many additions will be performed?
$endgroup$
– E.Coms
2 hours ago
$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
40 mins ago