The following is an algorithm for generating "Taxicab numbers" using a priority queue (
Vector is an arbitrary data type that allows for storage of two number and their cubed sum. For those unaware (although you really don't need to know), a taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: $a^3+b^3 = c^3+d^3$. An example would be $1729 = 12^3 + 1^3 = 10^3 + 9^3$.
for i = 1..n pq.insert( Vector(i^3+i^3,i,i) ) prev = Vector(0, 0, 0) while not pq.empty() curr = pq.deleteMin() if prev == curr print curr is a Taxicab number that can be expressed as prev^3 + prev^3 and curr^3 + curr^3 prev = curr if curr < N j = curr + 1 pq.insert( Vector(curr^3 + j^3, curr, j) )
I know inserting an item into the priority queue is $O(\log n)$ but I am not sure how this relates to space usage and runtime. Can someone help?