Kinetic heater

<h2 id="implementation">Implementation</h2>
If every element has a key and a priority associated with it, then there is a unique tree structure that is simultaneously a search tree on the keys and a heap on the priorities - this structure corresponds to the treap (if the priorities are randomly chosen) or the kinetic heater (if the keys are randomly chosen).
The validity of the tree structure is ensured by creating a certificate at each edge that enforces the heap property on that edge. The main operational difference between a kinetic heap and a kinetic heater is in how they respond to certificate failures. When a certificate on an edge fails, a kinetic heater will perform a rotation around the nodes that failed (instead of the swap that a kinetic heap would perform).
For example, consider the elements B (with parent F) and its left child D (with right child C). When the certificate [B>D] on the edge BD fails, the tree will be <a href="/facts/Tree_rotation/R3SlGyI0">rotated</a> around this edge. Thus in this case the resulting structure has D in place of B, C becomes a child of B instead ofD, and there are three certificate changes [B>D] replaced with [D>B], [D>C] replaced with [B>C] and [F>B] replaced with [F>D]. Everything else stays the same.

<h2 id="analysis">Analysis</h2>
This kinetic data structure is:

<ul><li><a href="/facts/Kinetic_data_structure/410CqBg7">Responsive</a>: There are O(1) certificate updates that need to be done when a certificate fails, which takes O(log n) time</li>
<li><a href="/facts/Kinetic_data_structure/410CqBg7">Local</a>: Each element is involved in O(1) certificates</li>
<li><a href="/facts/Kinetic_data_structure/410CqBg7">Compact</a>: There are O(n) total certificates</li>
<li><a href="/facts/Kinetic_data_structure/410CqBg7">Efficient</a>: It has the same (expected) asymptotic performance as <a href="/facts/Kinetic_hanger/5DIxY6ku">kinetic hanger</a>, <a href="/facts/Kinetic_tournament/HD0CL0d8">kinetic tournament</a> - for a collection of space-time trajectories where each pair intersects at most s times, the kinetic heater processes O(λs+2log n) events inO(λs+2log2n) time, where λs+2 is a <a href="/facts/Davenport-Schinzel_sequence/wsCPUu5B">Davenport-Schinzel sequence</a>.</li></ul>

<ul><li>Basch, J. <a href="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.41.2301&rep=rep1&type=pdf">"Kinetic Data Structures"</a>. Retrieved May 17, 2012.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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:1" class="footnote-back-ref">↩</a></li>
</ol>

Kinetic heater open-in-new

Kinetic heater