All you need to do is keep the books in a heap by their interestingness. ;) Then finding the most interesting book is Θ(1). It does take a little bit of work

All you need to do is keep the books in a heap by their interestingness. ;) Then finding the most interesting book is Θ(1). It does take a little bit of work to take it off the heap to see what's next on your reading list, though.