title: Heap-like data structure with fast random access?
body: <p>My situation is the following:</p>
  
  <ul>
  <li>I have a collection of entities, each of which has a "goodness" property.</li>
  <li>I wish to grab the entities one at a time, from "best" to "worst."</li>
  <li>After a "best" entity is grabbed, the "goodness" properties of several (relatively few) of my other entities change, and this change must be incorporated into my upcoming decision of the next "best" entity to grab.</li>
  <li>Some (relatively few) entities may become "worthless" after a grab, and these should be removed from my collection.</li>
  <li>It is easy for me to construct, given the entity that I just grabbed, the set of now-"dirty" objects, that is, the set of entities which potentially have a now-different "goodness," or have become "worthless."</li>
  </ul>
  
  <p>So, I need a data structure that allows me to:</p>
  
  <ul>
  <li>Quickly grab the "biggest" of a collection (as in, a max-heap).</li>
  <li>Quickly update the underlying ordering of the objects in my collection to accommodate the situation described above.  (Easy to do in a heap, if we can access the dirty objects' locations, e.g. array indices, within the underlying heap implementation.)</li>
  <li>There is a guarantee that there are no collisions among the entries of my collection.  (The entries are references to the entities I described above.)</li>
  </ul>
  
  <p>The idea I have is to use a max-heap together with an unordered map, keyed on the heap entries, and having values equal to, e.g., the objects' respective indices in the underlying array in the heap implementation.</p>
  
  <p>What I'm wondering is whether there may be a data structure which is better for this situation.</p>