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

[Rassska]

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]

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]

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]

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]

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]

This would be fantastic addition

[frangio]

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

[rocketman-21]

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]

This contract has been audited by c4

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