Faster kinetic heaps and their use in broadcast scheduling
Haim Y. Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis · Symposium on Discrete Algorithms · 2001
We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being fixed, is a linear function of time. The kinetic heap is a simple example of a kinetic data structure of the kind considered by Basch, Guibas, and Hershberger. Kinetic heaps have many applications in computational geometry, and previous implementations were designed to address these applications. We describe an additional application, to broadcast scheduling. Each of our kinetic heap implementations improves on previous implementations by being simpler or asymptotically faster for some or all applications.