A Kinetic Heater is a
kinetic priority queue A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum (or minimum) priority element (key-value pair) when the priority of every element is changing as a continuous func ...
similar to a
kinetic heap
A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities) where the priority is changing as a continuous function of time. As a type of kinetic priority ...
, that makes use of randomization to simplify its analysis in a way similar to a
treap. Specifically, each element has a random key associated with it in addition to its priority (which changes as a continuous function of time as in all
kinetic data structures). The kinetic heater is then simultaneously a
binary search tree on the element keys, and a
heap
Heap or HEAP may refer to:
Computing and mathematics
* Heap (data structure), a data structure commonly used to implement a priority queue
* Heap (mathematics), a generalization of a group
* Heap (programming) (or free store), an area of memory f ...
on the element priorities. The kinetic heater achieves (expected) asymptotic performance bounds equal to the best kinetic priority queues. In practice however, it is less efficient since the extra random keys need to be stored, and the procedure to handle certificate failure is a (relatively complicated) rotation instead of a simple swap.
Implementation
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
rotated around this edge. Thus in this case the resulting structure has ''D'' in place of ''B'', ''C'' becomes a child of ''B'' instead of''D'', and there are three certificate changes
>Dreplaced with
>B >Creplaced with
>Cand
>Breplaced with
>D Everything else stays the same.
Analysis
This kinetic data structure is:
*
Responsive: There are O(1) certificate updates that need to be done when a certificate fails, which takes O(log n) time
*
Local: Each element is involved in O(1) certificates
*
Compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
: There are O(n) total certificates
*
Efficient: It has the same (expected) asymptotic performance as
kinetic hanger,
kinetic tournament
A Kinetic Tournament is a kinetic data structure that functions as a priority queue for elements whose priorities change as a continuous function of time. It is implemented analogously to a "tournament" between elements to determine the "winner" ...
- for a collection of space-time trajectories where each pair intersects at most times, the kinetic heater processes events in time, where is a
Davenport-Schinzel sequence.
References
* {{cite web , url=http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.41.2301&rep=rep1&type=pdf , title=Kinetic Data Structures , accessdate=May 17, 2012, author=Basch, J
Kinetic data structures
Heaps (data structures)
Probabilistic data structures