Possible optimizations in the Heap

[QGarchery]

We can also implement:

• #38
• #36

Originally posted by @QGarchery in https://github.com/morpho-dao/morpho-data-structures/issues/23#issuecomment-1195113603

[MerlinEgalite]

Can we close? @QGarchery

[QGarchery]

I think we should do them in the basic heap, it should not be too difficult. The arguments against them for the use case of Morpho do not hold in general

[MerlinEgalite]

Ok tagging @makcandrov and @Tristan22400 on it

[makcandrov]

I'm not in favor of resolving #38 because it will increase gas consumption in general cases to save gas in a rare case where two accounts have the same value.

Regarding #36, it is correct that we can make the heap more usable by adding/replacing some functions. Which functions should be added?

• A function update instead of increase and decrease.
• A function pop that removes the first account of the heap.
• A function popAndInsert that removes the first account and inserts another account.

I'm in favor of the first two functions, but not the third.

[QGarchery]

I'm not in favor of resolving https://github.com/morpho-dao/morpho-data-structures/issues/38 because it will increase gas consumption in general cases to save gas in a rare case where two accounts have the same value.

I don't think we can assume that the rare case is when two accounts have the same value. I understand that there are use cases where indeed accounts should rarely have the same value (and that's why it's not implemented for Morpho, see this comment). But this implementation is meant as a general purpose heap, so we can make no assumption about how it's used.

I like the update function: it seems to be lightweight in terms of implementation and would be useful in a lot of cases