Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.
Some of the most common implementations are kinetic heaps which are simple to implement but don't have tight theoretical performance bounds, and their randomized variants - kinetic heaters and kinetic hangers - which are easier to analyze.
There is also a heap-like structure based on the dynamic convex hull data structure[1] which achieves better performance for affine motion of the priorities, but doesn't support curved trajectories.
It achieves, deterministically, the same performance bounds as the heater or hanger, however it is less local and responsive than the heap-based data-structures.
refers to a term in the Davenport-Schinzel sequence, which gives the maximum size of the upper envelope of
is the largest number of elements in the queue at any given time, while
refers to the total number of elements that are ever in the queue.