title: How to remove an arbitrary element from a standard heap in c++?
body: <p>I've got some code that continuously extracts the max valued object from a heap and processes it. However, during processing of the max, other objects in the heap are affected, and may need to get deleted. Roughly:</p>
  
  <pre><code>vector&lt;HeapEntry*&gt; myHeap = vector&lt;HeapEntry*&gt;();
  fillHeap(myHeap, someData);
  make_heap(myHeap.begin(), myHeap.end());
  while (!myHeap.empty())
  {
      HeapEntry* hp = myHeap.front();
      HeapEntry* neighbor = hp-&gt;getNeighbor();
      if (someCondition)
      {
          remove(myHeap, neighbor);
      }
      //more processing of hp
  }
  </code></pre>
  
  <p>And the remove function:</p>
  
  <pre><code>void remove(vector&lt;HeapEntry*&gt; myHeap, HeapEntry* toRemove)
  {
      for (it = myHeap.begin(); it != myHeap.end(); it++)
      {
          if (*it == hp)
          {
              myHeap.erase(it);
              break;
          }
      }
      make_heap(myHeap.begin(), myHeap.end());
  }
  </code></pre>
  
  <p>This runs and gives correct output. But it's slow as all hell: 2 minutes to process a 40kb file (the size of the heap is linear in the size of the file). Anyway it needs to be more efficient.</p>
  
  <p>The remove function ends up getting called roughly n times, where n is the size of the heap. So having that linear search makes the entire algorithm O(n^2). I think that's the problem, and I believe this can run in O(n*log(n)). </p>
  
  <p>My goal is to do the remove function in O(log(n)) time. Something like:</p>
  
  <ul>
  <li>Go straight to the target element</li>
  <li>Switch it with the last element</li>
  <li>pop_heap(myHeap.begin(), myHeap.end()); myHeap.pop_back();</li>
  <li>make_heap(myHeap.begin(), myHeap.end());</li>
  </ul>
  
  <p>I'm not quite sure how to implement this (I'm hardly familiar with the stl heap).
  Does anyone know how to do this without doing the linear search?</p>