Advice for Priority Queue w/ frequent swapping

I am creating a music playlist where each song is given a rank (not unique). The highest rated song will eventually be played and leave the queue. The catch is, each song can be up voted or down voted to change its rank, thus changing the order of the queue. Is there an ideal data structure for this behavior in elixir?

I have considered a list of song structs, but swapping elements in a list is not ideal. But to maintain order I can’t have a map of structs. Any help would be appreciated! (I’m new to elixir)

map of lists? rank -> list of songs with that rank?

But it sounds like maybe there’s no bounds on the rank, not 1-5 stars, but rather vote total. Thus there is no upper bound, and the actual rank values may be sparse, making it awkward to iterate over ranks.

You could easily keep track of the max rank, but then when you empty that list, you’d have to do something kind of gross like get the map keys and sort in order to find the next highest.

This could be an option. Wondering how I would iterate through the entire collection in order. Displaying the elements to a user. I guess I could check for every rank if it exists in the map, iterate through. But I was not going to provide an upper or lower bound (aka allowing negatives as well). Maybe I need to have a constraint for now.

You could track upper & lower, then iterate from lower to upper, handling the ones with no match. Or you could get the keys of the map into a list and sort it, then iterate that. Ok, map it, not iterate it :wink:

I like the idea of having a separate list for the ordered keys. Thanks!

Whats the advantage of using a list of keys instead of a list of the songs themselves? Either way you are ordering a list of references. OP I would just start with a list and Enum.sort_by and revisit this when you know performance is an issue.

1 Like

I think that’s a good idea before over complicating it. Just wanted to know if I was missing anything obvious as it had been bothering me. To update the list I would have to retrieve song, delete song in list, add song with updated rank and then sort? It seems like a lot for the task.

You can use Enum.find_index and List.replace_at, then Enum.sort_by. If you are getting lots of updates an easy optimization would be to apply them in a batch by putting them in a map and then mapping over the list; that way you only rebuild the list once per batch.

I think i’d consider an ets ordered set. From the docs:

If the data in the table is to be accessed so that the order of the keys in the table is significant, the table type ordered_set can be used instead of the more usual set table type. An ordered_set is always traversed in Erlang term order regarding the key field so that the return values from functions such as select, match_object, and foldl are ordered by the key values. Traversing an ordered_set with the first and next operations also returns the keys ordered.

That way updates are atomic and you could have multiple concurrent readers too.

1 Like

Oh wow I hadn’t seen that! Sounds like a perfect use case for what I’m after. Thank you!