search

OpenZeppelin / openzeppelin-contracts

OpenZeppelin Contracts is a library for secure smart contract development.
https://openzeppelin.com/contracts
MIT License
24.9k stars 11.78k forks source link

Add priority queue as a data structure to be able to implement max/min heaps #3410

Closed Rassska closed 3 months ago

Rassska commented 2 years ago

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

frangio commented 2 years ago

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?

Rassska commented 2 years ago

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. Also, I do have an extra question about sorting algorithms. Why they are not presented in OZ? At least some quick sort or etc?

frangio commented 2 years ago

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.

frangio commented 2 years ago

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.

Bijan-Massoumi commented 1 year ago

This would be fantastic addition

frangio commented 1 year ago

@Bijan-Massoumi Please share your use case so we can consider it for prioritization!

rocketman-21 commented 11 months ago

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.

rocketman-21 commented 9 months ago

This contract has been audited by c4

https://github.com/collectivexyz/revolution-protocol/blob/main/packages/revolution/src/culture-index/MaxHeap.sol