title: Algorithm to store elements of a list in a random order in a key/value store without a defined order, but retrieve max/min value
body: <p>While executing the application in question (a blockchain node, but regardless), every new block that comes over time has a number associated with it; The number is called &quot;ChainWork&quot;; it's a 256-bit number with a custom comparison function (not native to C++).</p>
  <p>The ChainWork associated with new blocks can theoretically have any value compared to the previous blocks' values. Because there are way too many blocks, assuming we don't want to store all the blocks (or even their ChainWork) in memory, we have to store them in a persistent storage.</p>
  <p>The only storage available is a key/value store that does not guarantee that these numbers are stored in order. There is not even a pre-defined storage order (think of it as a hash map).</p>
  <p><strong>The problem: We need to store these numbers in that persistent storage, but retrieve only the maximum value at will</strong></p>
  <p><strong>The question</strong>: Is there a way or algorithm that can make it possible to get the maximum value of the ChainWork values available at any point in time (and some associated information with them), provided that we can store any extra information required to help in retrieving the maximum value from the unsorted container? In other word, is there a way to reasonably sacrifice storage to get better complexity for this problem, instead of having to loop over all the ChainWork values, with O(N)?</p>
  <p>If you require any additional information, please go ahead and ask.</p>
  <p>EDIT: Keeping track of the max does not work because the max can be removed at times, so a re-loop over all the values would be required. I forgot to mention this point, but it came up in the comments. Apologies.</p>