A regular heap can be kinetized by augmenting with a certificate for every pair of nodes, such that is a child node of. If the value stored at a node is a function of time, then this certificate is only valid while. Thus, the failure of this certificate must be scheduled in the event queue at a time such that. All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take time.
Dealing with certificate failures
When a certificate fails, the data structure must swap and in the heap, and update the certificates that each of them was present in. For example, if was a child node of , and the certificate fails, then the data structure must swap and, then replace the old certificates , , , , with new certificates , , , and . Thus, assuming non-degeneracy of the events, only a constant number of events need to be de-scheduled and re-scheduled even in the worst case.
Operations
A kinetic heap supports the following operations:
: create an empty kinetic heap
: return the value stored in the heap at the current virtual time.
: insert a key into the kinetic heap at the current virtual time, whose value changes as a continuous function of time. The insertion is done as in a normal heap in time, but certificates might need to be changed as a result, so the total time for rescheduling certificate failures is
delete a key at the current virtual time. The deletion is done as in a normal heap in time, but certificates might need to be changed as a result, so the total time for rescheduling certificate failures is .
Performance
Kinetic heaps perform well according to the four metrics of kinetic data structure quality defined by Basch et al. The analysis of the first three qualities is straightforward:
Responsiveness: 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.
Locality: Each node is present in one certificate each along with its parent node and two child nodes, meaning that each node can be involved in a total of three scheduled events in the worst case, thus kinetic heaps are local.
Compactness: Each edge in the heap corresponds to exactly one scheduled event, therefore the number of scheduled events is exactly where is the number of nodes in the kinetic heap. Thus, kinetic heaps are compact.
The efficiency of a kinetic heap in the general case is largely unknown. However, in the special case of affine motion of the priorities, kinetic heaps are known to be very efficient.
Affine motion, no insertions or deletions
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 transitive closure of the tree structure of the heap, which is for a tree of height.
Affine motion, with insertions and deletions
If insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is However, this bound is not believed to be tight, and the only known lower bound is.
Variants
This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications, such as:
