3 ms·

I want to love this but it is missing things that I know of: - Fenwick tree - union-find algorithm / data structures Here is where I first saw Fenwick trees:

I want to love this but it is missing things that I know of: - Fenwick tree - union-find algorithm / data structures Here is where I first saw Fenwick trees: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array.

kadoban 3y ago
It does seem to be missing quite a bit. I was sure Fenwick had to be there under another name, but I don't see it. Union-find is an even weirder miss, that's a _great_ data structure and very useful. I couldn't think of any other term it'd be hiding under. The few I couldn't find off the top of my head: square-root decomposition, heavy-light decomposition and really anything at all on Range Minumum Query, one of my favorite general problems (IMO far more interesting than sorting as a group of techniques to focus some time on). > I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array. I think you usually see ufds on fixed arrays because it makes the algorithm analysis a bit more interesting. If you have lookups cost more than O(1) I think you'll wash out the fun parts of the analysis. The ds still works well of course regardless.
- xtiansimon 3y ago
  “… was sure Fenwick had to be there under another name.” Surely any ‘dictionary’ worth its salt would have cross references.
eru 3y ago
It's a very finite collection, obviously almost everything will be missing. That's inevitable. Eg they don't have a soft heap or a finger tree either. They are also missing many purely functional data structures that eg Okasaki talks about.

kadoban 3y ago

It does seem to be missing quite a bit. I was sure Fenwick had to be there under another name, but I don't see it. Union-find is an even weirder miss, that's a _great_ data structure and very useful. I couldn't think of any other term it'd be hiding under. The few I couldn't find off the top of my head: square-root decomposition, heavy-light decomposition and really anything at all on Range Minumum Query, one of my favorite general problems (IMO far more interesting than sorting as a group of techniques to focus some time on). > I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array. I think you usually see ufds on fixed arrays because it makes the algorithm analysis a bit more interesting. If you have lookups cost more than O(1) I think you'll wash out the fun parts of the analysis. The ds still works well of course regardless.

xtiansimon 3y ago
“… was sure Fenwick had to be there under another name.” Surely any ‘dictionary’ worth its salt would have cross references.

eru 3y ago

It's a very finite collection, obviously almost everything will be missing. That's inevitable. Eg they don't have a soft heap or a finger tree either. They are also missing many purely functional data structures that eg Okasaki talks about.