Add more data structures

[siriak]

Feel free to propose and/or implement new data structures, I will add them to the list below :) List of data structures that would be great to see in this repo: Basic:

• [x] Sorted List

Heaps:

• [x] Fibonacci heap
• [x] Pairing heap

Trees:

• [x] Scapegoat tree
• [ ] Finger tree
• [ ] Van Emde-Boas tree
• [x] Suffix trie
• [ ] B-tree
• [ ] B+ tree
• [ ] Interval tree
• [x] Red-Black tree
• [x] AVL-tree
• [ ] Splay-tree
• [ ] Merkle tree
• [ ] R-tree
• [ ] KD-tree
• [ ] Hash array mapped trie
• [ ] Ball tree

Probabilistic:

• [ ] Quotient filter

Other:

• [ ] Rope
• [ ] Skip list
• [ ] Zipper
• [x] Disjoint set
• [ ] Work Stealing Queue
• [x] Inverted index
• [ ] Gap buffer
• [ ] Nested sets
• [ ] Half-Edge data structure
• [x] Unrolled linked list

[ivanruski]

Hi @siriak, I think that Binary search tree should also be in the list, because it is easier to implement than AVL and Red-black trees. However it shares a lot of commonalities with them and this makes BST helpful when someone is starting to learn about trees to have a basic version.

[siriak]

Hi @ivanruski, sure thing! I've added Binary search tree to the list.

[antonykamp]

I could implement binary search tree and segment tree.

[jlechem]

Looks like the stacks are done, should update the list.

[rohansp]

@siriak I would like to contribute. any open issues ?

[siriak]

@rohansp you can take any algorithm/data structure that's not implemented yet and implement it.

[rohansp]

How to figure out which ones are implemented already?

On Mon, Oct 19, 2020 at 1:36 AM Andrii Siriak notifications@github.com wrote:

@rohansp https://github.com/rohansp you can take any algorithm/data structure that's not implemented yet and implement it.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/TheAlgorithms/C-Sharp/issues/112#issuecomment-711663511, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACVHOGE5QKPFCTNFHP2COZLSLPM75ANCNFSM4IUIZ7FQ .

[siriak]

You can check a list in README.md or browse directories in the repository and see in files. Also, here not implemented data structures are unchecked.

[mondalshubham1]

I want to contribute in AVL trees.

[arajaram]

Looks like AVL trees isn't done yet and I'm working on an implementation that I can contribute if it isn't done by the time I'm finished. Also going to take on Red-Black trees after I'm done with this.

[CyberMobius]

I can implement Fibonacci heaps

[siriak]

@arajaram @CyberMobius cool, go ahead!

[gedkott]

@siriak Do you think an implementation of a dynamic array would be worthwhile to add?

[siriak]

@gedkott IMO it'd be nice to have a dynamic array for educational purposes even though List exists, which is the same thing.

[gedkott]

@siriak That makes sense. Linked lists are part of the project already, but dynamic arrays would be a good educational addition to the project given the performance and implementation differences.

I have someone who is learning how to write a dynamic array now and I would like to have them contribute their complete solution here when ready. I'll be in touch as we progress. Let me know if there is anything we should consider as we work on it together.

Thanks for your leadership on this project!

[phougatv]

List (Dynamic Array)

[mime8]

Hi, I'd like to implement Scapegoat tree.

[phougatv]

List (Dynamic Array)

I would like to contribute. Do I need specific permission to create a branch and raise a PR?

[siriak]

@mime8 cool, go ahead! @phougatv you don't need any permission to contribute, just make a fork, work there and make a PR once you are done :)

[kolosovpetro]

@siriak Hi, do you need a graph implementation in the Data Structures section? (Via 2D matrix)

[siriak]

@kolosovpetro Hi, definitely :)

[mime8]

@siriak , hi again! I'll create a PR with Scapegoat tree implementation either today or early next week. Sorry for long absence.

[Leefrost]

Hi, I would like to work with Fenwick tree (#245)

[Leefrost]

I can take Pairing heap [#248] and Unrolled linked list [#251]

[slorello89]

I'd be happy to do a bloom filter

[Leefrost]

If no one takes already Inverted index, I will do it [#262]

[kaydotdev]

Hey @siriak, what do you think about Matrix (Tensor) data structure with corresponding operators, like element-wise arithmetics, multiplication, determinant, invert e.t.c?

[siriak]

@antonAce that's a nice idea, I like it :)

[mime8]

I'd like to work on B-tree next, if that's okay.

[mime8]

BTW, I think the description of this thread should be updated. Some of the data structures mentioned there are already implemented.

[siriak]

@mime8 I think I've updated it correctly, please let me know if something else was already implemented

[mime8]

@siriak , I see that SortedList and AVL tree were already implemented.

[deljohnson1]

We need a BigList. The implementation of List in C# is constrained by an integer index.

[siriak]

Let's keep track of new proposals as separate issues