Priority_queue Vs make_heap

Question

Problem statement :

we have a vector as an input.
task is to
A. find out first two maximum numbers
B. remove biggest number from vector
C. add number to vector which is abdolute difference of two numbers found in step A
D. print two numbers found in step A

repeat steps A to D three times

Query :
What is best method to achieve the same ? Method1 or Method 2? i.e. priority_queue or make_heap ?

Reference code :
https://code.sololearn.com/c0r55VJ1GZz6/?ref=app

Answer 1

iirc priority queues are usually implemented as heaps so without knowing better I'm sure both are fine and equally performant. I think I'm partial towards priority queues because what you are doing sounds exactly like what that data structure is designed to do.

Never hurts to run some performance benchmarks though. :)

Or if you want to optimize hard you could simply grab the 6 largest numbers in your list and produce the desired output based on that. That must be more performant than building a heap from the entire input list, though both approaches are O(n).

Answer 2

In terms of efficiency, they seem about the same:
https://code.sololearn.com/ca19a2313A18/?ref=app
https://code.sololearn.com/ca204a395a16/?ref=app

Answer 3

Thanks Schindlabua nd Edward Finkelstein