Faster kinetic heaps and their use in broadcast scheduling
Faster kinetic heaps and their use in broadcast scheduling
复制标题
更快的动态堆及其在广播调度中的应用
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Kostas Tsioutsiouliklis
中科院分区：
文献类型：
--
作者：
Haim Kaplan;R. Tarjan;Kostas Tsioutsiouliklis
我们描述了动力学堆的几个实现，这是一个堆（优先队列），其中每个项目的密钥（而不是固定）是时间的线性函数。动力学堆是Basch，Guibas和Hershberger认为的动力学数据结构的一个简单示例。动力学堆在计算几何形状中具有许多应用，并且以前的实现旨在解决这些应用程序。我们描述了一个其他应用程序，以广播计划。对于某些或所有应用程序，我们的每个动力学堆实现都会通过更简单或渐近的速度来改善以前的实现。
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.