title: Sorting data structure: random in, lowest out
body: <p>I need a data structure that supports the insertion of key-value pairs, and the extraction of the pair with the lowest key. Insertion and extraction can happen at any time, thus the data structure must remain continuously sorted, and extraction includes the removal of the pair from the list. Additionally, no new pair that is being inserted can have a key lower in value than the key of the most recently extracted pair. The keys of the pairs being inserted will also increase in value over time.</p>
  
  <p>Requirements:</p>
  
  <ul>
  <li>Key: 64-bit unsigned integer</li>
  <li>Maximum number of entries listed at any one time: ~10^6</li>
  <li>Entries inserted (and extracted) per second: ~10^5</li>
  <li>Efficient removal of entries upon extraction</li>
  <li>Keys of pairs being inserted: current lowest key > key > current lowest key + 10^7</li>
  <li>Memory requirements are irrelevant, computational complexity is not</li>
  <li>Some pairs can have the same key</li>
  </ul>