# Solutions to Diophantine Equations using a Min Heap

I've recently come across this problem:

Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$. Hint: use one min-heap and one max-heap.

I can think of an algorithm involving two min-heaps (one for the LHS and one for the RHS), but can't figure out how a max-heap can be used. It needs to be efficient.

How could a max-heap be incorporated?

• The solution you have in mind could be a variant on the solution the setter had in mind. Don't take the hint as scripture. – Yuval Filmus Feb 11 '16 at 10:39
• If you have created two accounts, I encourage you to merge them: cs.stackexchange.com/help/merging-accounts. Thank you! – D.W. Feb 11 '16 at 12:27

A min-heap with entries $x_i$ is equivalent to a max-heap with entries $-x_i$ (or more generally, $A - Bx_i$ for any $B > 0$, or even more generally, $\phi(x_i)$ for any monotone decreasing $\phi$). So you can convert your solution with two min-heaps to a solution with one min-heap and one max-heap, as well as to a solution with two max-heaps.