A priority queue based Fibonacci heap appears to be the best solution as at least one direction of the mutation of the priority (increase or decrease depending on implementation) is O(1) while the other is O(log N), see http://www.boost.org/doc/libs/1_52_0/doc/html/heap/data_structures.html
A priority queue based Fibonacci heap appears to be the best solution as at least one direction of the mutation of the priority (increase or decrease depending on implementation) is O(1) while the other is O(log N), see http://www.boost.org/doc/libs/1_52_0/doc/html/heap/data_structures.html