title: Easiest way of using min priority queue with key update in C++
body: <p>Sometimes during programming contests etc., we need a simple working implementation of min priority queue with decrease-key to implement Dijkstra algorithm etc.. I often use set&lt; pair&lt;key_value, ID&gt; &gt; and an array (mapping ID-->key_value) together to achieve that. </p>
  
  <ul>
  <li><p>Adding an element to the set takes O(log(N)) time. To build a priority queue out of N elements, we simply add them one by one into the set. This takes O(N log(N)) time in total.</p></li>
  <li><p>The element with min key_value is simply the first element of the set. Probing the smallest element takes O(1) time. Removing it takes O(log(N)) time.</p></li>
  <li><p>To test whether some ID=k is in the set, we first look up its key_value=v_k in the array and then search the element (v_k, k) in the set. This takes O(log(N)) time.</p></li>
  <li><p>To change the key_value of some ID=k from v_k to v_k', we first look up its key_value=v_k in the array, and then search the element (v_k, k) in the set. Next we remove that element from the set and then insert the element (v_k', k) into the set. We then update the array, too. This takes O(log(N)) time.</p></li>
  </ul>
  
  <p>Although the above approach works, most textbooks usually recommend using binary heaps to implement priority queues, as the time of building the binary heaps is just O(N). I heard that there is a built-in priority queue data structure in STL of C++ that uses binary heaps. However, I'm not sure how to update the key_value for that data structure.</p>
  
  <p>What's the easiest and most efficient way of using min priority queue with key update in C++?</p>