dPQ

dPQ, short for dynamic Priority Queue, is a data structure that maintains a set of elements, each with an associated priority, while allowing changes to an element's priority after it has been inserted. Unlike a static or fixed-priority queue, the dPQ supports efficient priority updates, enabling algorithms that repeatedly adjust priorities without removing and reinserting elements.

Operations typically include insert(element, priority), peek or minimum, extract-min, and update-priority(element, newPriority). Some variants also allow direct decrease-key and increase-key operations, while others rely on remove and reinsert. The interface is designed to support both single-element updates and bulk re-prioritization when needed.

Implementation approaches combine a heap-based structure with an index or handle map that tracks each element’s position in the underlying storage. Common choices include augmented binary, binomial, or Fibonacci heaps, as well as pairing heaps, all augmented with a hash map or array to locate elements quickly. Bucketed or radix-based variants may be used when priorities are integral and bounded, trading generality for speed.

Time complexities depend on the chosen implementation. Insert and update-priority typically run in O(log n) with heap-based structures, while extract-min is also O(log n). Some specialized variants aim for near-constant time updates under specific conditions, often at the cost of higher memory usage or restricted priority domains. Practical performance hinges on the frequency of updates and the size of the data set.

Applications of dPQ include discrete-event simulation, shortest-path and search algorithms that require dynamic re-prioritization, real-time task scheduling, and network routing where task priorities change over time. Limitations include implementation complexity and potential overhead, making simpler priority queues preferable when priorities are immutable.