Priority Queue Classes with Priority Update

A limitation in the design of the interface of C++ containers (i.e., data structure implementations) is addressed. Priority queues and their use in Dijkstra's shortest path search algorithm are used as an example. Priority queues are often implemented using heaps. There is a problem, however: it may be necessary to change the priority of an element while it is in the queue, but finding the element from within a heap is costly. The problem may be solved by keeping track, in a variable that is outside the heap, of the position of the element in the heap. Unfortunately, this is impossible with the template class interface used by the C++ standard library priority queue. In this research, the problem is analysed in detail. Three interface designs and the corresponding implementations are suggested. They are compared experimentally to each other and the C++ design.