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 property – if B is a child node of A, then the priority of the element in A must be higher than the priority of the element in B. 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.
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).
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.
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.
For example, if B (with child nodes Y and Z) was a child node of A (with child nodes B and C and parent node 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].
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.
A kinetic heap supports the following operations:
Kinetic heaps perform well according to the four metrics ( responsiveness, locality, compactness and efficiency) of kinetic data structure quality defined by Basch et al. [1] The analysis of the first three qualities is straightforward:
The efficiency of a kinetic heap in the general case is largely unknown. [1] [2] [3] However, in the special case of affine motion f(t) = at + b of the priorities, kinetic heaps are known to be very efficient. [2]
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 O(nlogn) for a tree of height O(logn). [2]
If n insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is [4] However, this bound is not believed to be tight, [2] and the only known lower bound is . [4]
This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications, [5] such as:
Other heap-like kinetic priority queues are:
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)
{{
cite web}}
: CS1 maint: multiple names: authors list (
link)
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)[
permanent dead link]
Guibas, Leonidas. "Kinetic Data Structures - Handbook" (PDF). Archived from the original (PDF) on 2007-04-18. Retrieved May 17, 2012.
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 property – if B is a child node of A, then the priority of the element in A must be higher than the priority of the element in B. 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.
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).
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.
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.
For example, if B (with child nodes Y and Z) was a child node of A (with child nodes B and C and parent node 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].
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.
A kinetic heap supports the following operations:
Kinetic heaps perform well according to the four metrics ( responsiveness, locality, compactness and efficiency) of kinetic data structure quality defined by Basch et al. [1] The analysis of the first three qualities is straightforward:
The efficiency of a kinetic heap in the general case is largely unknown. [1] [2] [3] However, in the special case of affine motion f(t) = at + b of the priorities, kinetic heaps are known to be very efficient. [2]
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 O(nlogn) for a tree of height O(logn). [2]
If n insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is [4] However, this bound is not believed to be tight, [2] and the only known lower bound is . [4]
This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications, [5] such as:
Other heap-like kinetic priority queues are:
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)
{{
cite web}}
: CS1 maint: multiple names: authors list (
link)
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)[
permanent dead link]
Guibas, Leonidas. "Kinetic Data Structures - Handbook" (PDF). Archived from the original (PDF) on 2007-04-18. Retrieved May 17, 2012.