News for hackers. Stuff that matters.

A comment on Ask HN: What are some cool but obscure data structures you know about?. Parent comment

Re:Ask HN: What are some cool but obscure data structures yo... by hexomancer on Friday July 22, 2022 @03:05AM (#32189358)
I have always wanted to really understand this data structure. Sure, I can follow the analysis with the potential functions and all, but I never really understood how Tarjan came up with the functions in the first place. Does anybody have a resource which intuitively explains the analysis?
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by hashingroll on Friday July 22, 2022 @04:29AM (#32189838)
This might a long read but it is well-written reader-friendly analysis of Tarjan's proof with chain of reasoning. https://codeforces.com/blog/entry/98275
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by sn9 on Friday July 22, 2022 @03:13PM (#32195976)
Robert Sedgewick has a great explanation in his Algorithms book. He has gorgeous diagrams alongside his explanations.
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by hexomancer on Friday July 22, 2022 @03:56PM (#32196399)
Is it in an old edition? I just downloaded an extremely legitimate version of Algorithms 4th edition but it has no section on union data structure.
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by sn9 on Friday July 22, 2022 @06:01PM (#32197611)
It should be in Chapter 1 Section 5 of the 4th edition. It's even in the table of contents.
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by hexomancer on Saturday July 23, 2022 @03:43AM (#32201274)
Sorry, my bad. I searched for the word "disjoint" expecting it to be prominent in this section but somehow this word only appears 3 times in this book non of which are in this section!

Anyway, while the figures in this work were indeed gorgeous, it was not what I was looking for. It did not even contain a non-intuitive analysis of the inverse ackermann complexity, much less an intuitive one!

[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by simonlindholm on Friday July 22, 2022 @05:25AM (#32190165)
Here's a writeup I made a while ago: https://www.overleaf.com/read/hjbshsqmjwpg
[ Parent | on HN ]