Along with what @aya_cool
said, Instead of Heap you could use Priority Queue and also keep in mind the number of insertions since it is a costly operation, this can be done by keeping a map in check of the numbers which are already present in the PriorityQueue. Or you could use Some Data Structures like TreeMap in Java, in case you do in Java. TreeMap is a combination of HashMap and sorted Keys based on Custom Comparator (might be ascending or descending here in case descending). Hope it helpsâ€¦

Actually priority queue is an abstract data structure, which is usually implemented as a heap. So using a priority queue instead of a heap does not make sense.

Yes, i understand that I meant as in inbuilt Data Structure i.e. STL Container Adapter std::priority_queue. Even Tree Map uses RB Tree, for implementation, thatâ€™s what i was trying to point out. But where efficiency matters, you wont prefer writing whole MaxHeapify functions.

First, sort the arrays A and B. Then initialize a max heap with the tuple (A[n-1]+B[n-1],\ n,\ n). You can use a priority_queue in C++ and a TreeMap in Java as @ssaxena36 has said. The heap should be ordered by the first value, the order of the rest does not matter. Then pop the heap to get the current largest sum and the indices of the elements in A and B which make up this sum. Let this popped tuple be (sum,\ i,\ j). Next insert (A[i]+B[j-1],\ i,\ j-1) and (A[i-1]+B[j],\ i-1,\ j) into the heap. Repeat this procedure n times to get the n largest sums.