title: Fast(est) Mutable Heap Implementation in C++
body: <p>I'm currently looking for the fastest data structure in C++ that fulfils my requirements:</p>
  
  <ol>
  <li>I start with a few million entries which need to be inserted.</li>
  <li>In each iteration I want to peek at the maximum element and update
  around 10 other elements. I even could do with only decreasing keys, but I would prefer an update (increase and decrease functionality).</li>
  </ol>
  
  <p>I don't need deletes/insertions (apart from the initial one) nor anything else. I thought a heap would be the preferable choice. After looking into the STL I found that most data structures do not support an update (which is the crucial part). The solution would be to delete and reinsert the elements which seems to be quite slow (bottleneck of my program). I then looked at the heaps provided by boost and found that the pairing_heap gives me the best results. All heaps are, however, still slower than the delete/insert process on a MultiMap. Does anybody have a suggestion, which other approach/implementation I could try?</p>
  
  <p>Thank you very much. </p>
  
  <p>Again for completeness sake, here are my current timings:</p>
  
  <ol>
  <li>MultiMap STL (delete/insert): ~70 sec</li>
  <li>Fibonacci Boost: ~110 sec</li>
  <li>D-Ary Heap Boost ~(best choice: D=150): ~120 sec </li>
  <li>Pairing Heap Boost: ~90 sec</li>
  <li>Skew Heap Boost: 105 sec</li>
  </ol>
  
  <p>Edited my post to clarify a few things:</p>
  
  <ol>
  <li>My entries are doubles (double is the key, I still have some arbitrary value attached to it) that is why I don't think that hashing is a good idea.</li>
  <li>I was talking about a PriorityQueue which was incorrect. Instead the first implementation used a MultiMap where the values would be erased and then reinserted (with the new value). I updated my post. Sorry for the confusion.</li>
  <li>I don't see how std::make_heap can solve this problem.</li>
  <li>To update the elements I have a separate lookup table in which I maintain a handle to the element. With that I can directly update the element without searching for it.</li>
  </ol>