title: Data structure with quick min, delete, insert, search for big compute job
body: <p>I'm looking for a data structure that will let me perform the operations I need efficiently. I expect to traverse a loop between 10<sup>11</sup> and 10<sup>13</sup> times so Ω(<em>n</em>) operations are right out. (I'll try to trim <em>n</em> down so it can fit in cache but it won't be small.) Each time through the loop I will call</p>
  <ul>
  <li>Min exactly once</li>
  <li>Delete exactly once (delete the minimum, if that helps)</li>
  <li>Insert 0 to 2 times, with an average of somewhat more than 1</li>
  <li>Search once for each insert</li>
  </ul>
  <p>I only care about average or amortized performance, not worst-case. (The calculation will take ages, it's no concern if bits of the calculation stall from time to time.) The data will not be adversarial.</p>
  <p>What kinds of structures should I consider? Maybe there's some kind of heap modified to have quick search?</p>