Is a heap the right structure? The "adjust_heap" operation must have a time complexity of some significance. I too thought of a heap at first, but can't get around the thought that adjusting the priority of potentially every single song, once per second, seems like it would mean re-heaping potentially the entire structure once per second.

I hope I'm wrong. ;)