https://en.wikipedia.org/wiki/Median_mechanism
Keep a min heap and a max heap in two solidity arrays.
If a new vote is greater than root of the min heap, insert it there, otherwise insert it in the max heap.
If the difference of the sizes of the heaps is one or less, you’re done, otherwise remove the root from the larger one and insert it into the smaller one.
Find the current median by looking at the root of the larger heap. If they’re the same size, take the average of the two roots.
- https://github.com/eliphang/spicy-combos-contracts/blob/main/PriQueue.sol
- https://github.com/zmitton/eth-heap#max-heap--min-heap
- https://github.com/Dev43/heap-solidity/tree/master#heaps
After you insert or remove an item, you need to preserve the heap property, which requires up to log(n) updates, so that could be triggered up to 3 times when you vote (once to insert your vote and once more per heap if a value needs to be moved from one heap to the other).
We should also keep the locations of all values in a map, so votes can be located in the heap to be updated. That means that any update to a heap would also require an update to the map. Voting would require up to two inserts and up to 6 * log(n) updates. Replacing your vote would require up to 6 * log(n) updates with no inserts. Updating a value costs 1/4 as much as inserting. See https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2200.md So adding a vote to a list of votes that already had 10 billion votes in it would require one or two inserts and 0 to 200 updates. The max gas for that would be 1 million (200 * 5000), but 30,000 (6 * 5000) is more likely. So if gas is 10 gwei that puts the cost in the range of .0003 to .01 currency units. (xdai, eth, etc.) This is affordable on all chains except mainnet. ↩︎