Chatting about data structures with colleagues, and one mentioned a "left-leaning red-black tree".
I guess in a left-leaning red-black tree, the algorithms ensure that every node receives a reasonable minimum amount of processing. Whereas in a right-leaning red-black tree, the nodes all just get to compete with each other in a free market.
I'd normally use binomial heaps for that merging application (on the rare occasion that I need it at all). Those also have O(log n) worst-case time for a merge. I can't work out in 30 seconds which structure is better, though!
@simontatham Oh yeah, I completely forgot about binomial heaps!
I'm a huge fan of Fibonacci heaps, which can be merged in constant amortized time! Sadly, they involve a lot of pointer operations so they aren't all that useful in practice.
@a I have to confess that despite being a huge data-structures nerd in most other respects, I've never quite managed to get my head round how a Fibonacci heap works. I understand what useful properties it has, and why that makes it a good fit for e.g. Dijkstra's algorithm, but how it works just never quite comes together in my brain.
Add comment