Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Kinetic heap
open-in-new
<h2 id="implementation-and-operations">Implementation and operations</h2> <p>A regular heap can be kinetized by augmenting with a certificate [A>B] for every pair of nodesA, B such that B is a child node of A. If the value stored at a node X is a function fX(t) of time, then this certificate is only valid while fA(t) > fB(t). Thus, the failure of this certificate must be scheduled in the event queue at a time t such that fA(t) > fB(t). </p><p>All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take O(log n) time. </p> <h3>Dealing with certificate failures</h3> <p>When a certificate [A>B] fails, the data structure must swap A and B in the heap, and update the certificates that each of them was present in. </p><p>For example, if B (with <a href="/facts/Child_node/RcXz9noF">child nodes</a> Y and Z) was a child node of A (with child nodes B and C and <a href="/facts/Parent_node/RcXz9noF">parent node</a> X), and the certificate [A>B] fails, then the data structure must swap B and A, then replace the old certificates (and the corresponding scheduled events) [A>B], [A<X], [A>C], [B>Y], [B>Z] with new certificates [B>A], [B<X], [B>C], [A>Y] and [A>Z]. </p><p>Thus, assuming <a href="/facts/Degeneracy_(mathematics)/BqhqlXPH">non-degeneracy</a> of the events (no two events happen at the same time), only a constant number of events need to be de-scheduled and rescheduled even in the worst case. </p> <h3>Operations</h3> <p>A kinetic heap supports the following operations: </p> <ul><li>create-heap(h): create an empty kinetic heap h</li> <li>find-max(h, t) (or find-min): – return the max (or min for a min-heap) value stored in the heap h at the current virtual time t.</li> <li>insert(X, fX, t): – insert a key X into the kinetic heap at the current virtual time t, whose value changes as a continuous function fX(t) of time t. The insertion is done as in a normal heap in O(log n) time, but O(log n) certificates might need to be changed as a result, so the total time for rescheduling certificate failures is O(log 2 n)</li> <li>delete(X, t) – delete a key X at the current virtual time t. The deletion is done as in a normal heap in O(log n) time, but O(log n) certificates might need to be changed as a result, so the total time for rescheduling certificate failures is O(log 2 n).</li></ul> <h2 id="performance">Performance</h2> <p>Kinetic heaps perform well according to the four metrics (<a href="/facts/Kinetic_data_structure/410CqBg7">responsiveness</a>, <a href="/facts/Kinetic_data_structure/410CqBg7">locality</a>, <a href="/facts/Kinetic_data_structure/410CqBg7">compactness</a> and <a href="/facts/Kinetic_data_structure/410CqBg7">efficiency</a>) of kinetic data structure quality defined by Basch et al.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> The analysis of the first three qualities is straightforward: </p> <ul><li><a href="/facts/Kinetic_data_structure/410CqBg7">Responsiveness</a>: A kinetic heap is responsive, since each certificate failure causes the concerned keys to be swapped and leads to only few certificates being replaced in the worst case.</li> <li><a href="/facts/Kinetic_data_structure/410CqBg7">Locality</a>: Each node is present in one certificate each along with its parent node and two child nodes (if present), meaning that each node can be involved in a total of three scheduled events in the worst case, thus kinetic heaps are local.</li> <li><a href="/facts/Kinetic_data_structure/410CqBg7">Compactness</a>: Each edge in the heap corresponds to exactly one scheduled event, therefore the number of scheduled events is exactly n-1 where n is the number of nodes in the kinetic heap. Thus, kinetic heaps are compact.</li></ul> <h3>Analysis of efficiency</h3> <p>The efficiency of a kinetic heap in the general case is largely unknown.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> However, in the special case of <a href="/facts/Kinetic_data_structure/410CqBg7">affine motion</a> f(t) = at + b of the priorities, kinetic heaps are known to be very efficient.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <h4>Affine motion, no insertions or deletions</h4> <p>In this special case, the maximum number of events processed by a kinetic heap can be shown to be exactly the number of edges in the <a href="/facts/Transitive_closure/HEtgYGM4">transitive closure</a> of the tree structure of the heap, which is O(nlogn) for a tree of height O(logn).<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h4>Affine motion, with insertions and deletions</h4> <p>If n insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is O ( n n log n ) . {\displaystyle O(n{\sqrt {n\log n}}).} <a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> However, this bound is not believed to be tight,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> and the only known lower bound is Ω ( n log n ) {\displaystyle \Omega (n\log n)} .<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <h2 id="variants">Variants</h2> <p>This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> such as: </p> <ul><li>Fibonacci kinetic heap</li> <li>Incremental kinetic heap</li></ul> <p>Other heap-like kinetic priority queues are: </p> <ul><li><a href="/facts/Kinetic_heater/4lscICR4">Kinetic heater</a></li> <li><a href="/facts/Kinetic_hanger/5DIxY6ku">Kinetic hanger</a></li></ul> <p>Guibas, Leonidas. <a href="https://wayback.archive-it.org/all/20070418010021/http://graphics.stanford.edu/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf">"Kinetic Data Structures - Handbook"</a> (PDF). Archived from <a href="http://graphics.stanford.edu/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf">the original</a> (PDF) on 2007-04-18. Retrieved May 17, 2012. </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747–756. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link) <a href="http://dl.acm.org/citation.cfm?id=314435" target="_blank">http://dl.acm.org/citation.cfm?id=314435</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747–756. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link) <a href="http://dl.acm.org/citation.cfm?id=314435" target="_blank">http://dl.acm.org/citation.cfm?id=314435</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>da Fonseca; Guilherme D.; de Figueiredo; Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012. <a href="https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf" target="_blank">https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. "Kinetic hanger" (PDF). Information Processing Letters. pp. 151–157. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.{{cite web}}: CS1 maint: multiple names: authors list (link) <a href="https://web.archive.org/web/20150524111432/http://www.uniriotec.br/~fonseca/hanger.pdf" target="_blank">https://web.archive.org/web/20150524111432/http://www.uniriotec.br/~fonseca/hanger.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>da Fonseca; Guilherme D.; de Figueiredo; Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012. <a href="https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf" target="_blank">https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>da Fonseca; Guilherme D.; de Figueiredo; Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012. <a href="https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf" target="_blank">https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Basch, J, Guibas, L. J., Ramkumar, G. D. (1997). "Sweeping lines and line segments with a heap". Proceedings of the thirteenth annual symposium on Computational geometry. SCG. ACM. pp. 469–471. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link) <a href="http://dl.acm.org/citation.cfm?id=263089" target="_blank">http://dl.acm.org/citation.cfm?id=263089</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>da Fonseca; Guilherme D.; de Figueiredo; Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012. <a href="https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf" target="_blank">https://web.archive.org/web/20150524004957/http://www.uniriotec.br/~fonseca/kh.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Basch, J, Guibas, L. J., Ramkumar, G. D. (1997). "Sweeping lines and line segments with a heap". Proceedings of the thirteenth annual symposium on Computational geometry. SCG. ACM. pp. 469–471. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link) <a href="http://dl.acm.org/citation.cfm?id=263089" target="_blank">http://dl.acm.org/citation.cfm?id=263089</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>K. H., Tarjan, R. and T. K. (2001). "Faster kinetic heaps and their use in broadcast scheduling" (PDF). Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM. pp. 836–844. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link)[permanent dead link] <a href="http://wwwnew.cs.princeton.edu/courses/archive/fall03/cs528/handouts/faster%20kinetic%20heaps.pdf" target="_blank">http://wwwnew.cs.princeton.edu/courses/archive/fall03/cs528/handouts/faster%20kinetic%20heaps.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>