Rotating title picker for a home-page billboard

Build a component that picks which title to show next in a billboard (or plays next in a playlist). Every title has a relevance score, and scores can change at any time. Each call to get() returns one title, highest score first, and within one pass over the catalog no title is returned twice; when every title has been shown, a new pass starts.

Discuss the data structures for fast get() and score updates, what an update means for a title already shown in this pass, and then make it thread-safe.