-
Notifications
You must be signed in to change notification settings - Fork 11.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We鈥檒l occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add priority queue as a data structure to be able to implement max/min heaps #3410
Comments
A heap data structure would be a pretty cool addition. O(log n) queue and dequeue operations are acceptable. Can you please give example use cases? |
Okay, I'll provide it a bit later. |
Sorting algorithms are O(n log n) so they may run out of gas with large arrays, which may be manipulable by users and become an attack vector. Specific contracts may have reasonable bounds on array length but we err on the conservative side to help people avoid creating an attack vector unknowingly. A min/max heap will be a good alternative for use cases that require sorting. |
Hm, I'm not sure Fibonacci heaps are acceptable for this context. I have to admit I'm not super familiar with them but they apparently can have high overhead which will probably translate to expensive storage operations, and worst case complexity is linear. |
This would be fantastic addition |
@Bijan-Massoumi Please share your use case so we can consider it for prioritization! |
I just implemented this w/associated tests. Will open a PR / can share code if y'all want. Use case is an open submission box that anyone can submit to, and a specific set of accounts can vote on submissions, and gas-efficiently pull off the top voted submission. |
This contract has been audited by c4 |
Hi, there! Thank you so much for such great source!
馃 Motivation
I'm operating with huge amount of data in my smart contracts and sometimes it's pretty useful to handle queries by simply implementing common data structures in terms of saving more gas. We already do have a dequeue/bitmaps impls and now I want to add a priority queue if it's possible.
Let me know, what do you think about it <3
馃摑 Details
The text was updated successfully, but these errors were encountered: