Kinetic heap

File:Kinetic heap overview.png

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 queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap propertyTemplate:Snd if Template:Math is a child node of Template:Math, then the priority of the element in Template:Math must be higher than the priority of the element in Template:Math. This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue (the event queue) to maintain certificate failure times.

Implementation and operations

A regular heap can be kinetized by augmenting with a certificate [[[:Template:Math]]] for every pair of nodesTemplate:Math, Template:Math such that Template:Math is a child node of Template:Math. If the value stored at a node Template:Math is a function Template:Math of time, then this certificate is only valid while Template:Math. Thus, the failure of this certificate must be scheduled in the event queue at a time Template:Math such that Template:Math.

All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take Template:Math time.

Dealing with certificate failures

File:Kinetic heap swap.png

When a certificate [[[:Template:Math]]] fails, the data structure must swap Template:Math and Template:Math in the heap, and update the certificates that each of them was present in.

For example, if Template:Mvar (with child nodes Template:Mvar and Template:Mvar) was a child node of Template:Mvar (with child nodes Template:Mvar and Template:Mvar and parent node Template:Mvar), and the certificate [[[:Template:Math]]] fails, then the data structure must swap Template:Mvar and Template:Mvar, then replace the old certificates (and the corresponding scheduled events) [[[:Template:Math]]], [[[:Template:Math]]], [[[:Template:Math]]], [[[:Template:Math]]], [[[:Template:Math]]] with new certificates [[[:Template:Math]]], [[[:Template:Math]]], [[[:Template:Math]]], [[[:Template:Math]]] and [[[:Template:Math]]].

Thus, assuming non-degeneracy 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.

Operations

A kinetic heap supports the following operations:

• Template:Math: create an empty kinetic heap Template:Math
• Template:Math (or find-min):Template:Snd return the Template:Math (or Template:Math for a Template:Math) value stored in the heap Template:Math at the current virtual time Template:Math.
• Template:Math:Template:Snd insert a key Template:Math into the kinetic heap at the current virtual time Template:Math, whose value changes as a continuous function Template:Math of time Template:Math. The insertion is done as in a normal heap in Template:Math time, but Template:Math certificates might need to be changed as a result, so the total time for rescheduling certificate failures is Template:Math
• Template:MathTemplate:Snd delete a key Template:Math at the current virtual time Template:Math. The deletion is done as in a normal heap in Template:Math time, but Template:Math certificates might need to be changed as a result, so the total time for rescheduling certificate failures is Template:Math.

Performance

Kinetic heaps perform well according to the four metrics (responsiveness, locality, compactness and efficiency) 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 (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.
• Compactness: Each edge in the heap corresponds to exactly one scheduled event, therefore the number of scheduled events is exactly Template:Math where Template:Math is the number of nodes in the kinetic heap. Thus, kinetic heaps are compact.

Analysis of efficiency

The efficiency of a kinetic heap in the general case is largely unknown. However, in the special case of affine motion Template:Math 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 Template:Math for a tree of height Template:Math.

Affine motion, with insertions and deletions

If Template:Math insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is $O(n\sqrt{n\log n}).$ However, this bound is not believed to be tight, and the only known lower bound is $\mathrm{\Omega }(n\log n)$.

Variants

This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications, such as:

• Fibonacci kinetic heap
• Incremental kinetic heap

Other heap-like kinetic priority queues are:

• Kinetic heater
• Kinetic hanger