EN

Kinetic priority queue

January 8, 2022
article

A Kinetic Priority Queue is an abstractkinetic 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 function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.

. . . Kinetic priority queue . . .

The operations supported are:

  • create-queue(q): create an empty kinetic priority queue q
  • find-max(q, t) (or find-min): – return the max (or min for a min-queue) value stored in the queue q at the current virtual time t.
  • insert(X, fX, t): – insert a key X into the kinetic queue at the current virtual timet, whose value changes as a continuous function fX(t) of time t.
  • delete(X, t) – delete a key X at the current virtual time t.

There are several variants of kinetic priority queues, which support the same basic operations but have different performance guarantees. Some of the most common implementations are kinetic heaps which are simple to implement but don’t have tight theoretical performance bounds, and their randomized variants – kinetic heaters and kinetic hangers – which are easier to analyze. There is also a heap-like structure based on the dynamic convex hull data structure[1] which achieves better performance for affine motion of the priorities, but doesn’t support curved trajectories. The kinetic tournament is another commonly used implementation. It achieves, deterministically, the same performance bounds as the heater or hanger, however it is less local and responsive than the heap-based data-structures.

Time complexities of kinetic priority queue implementations [2]
Trajectory of element priorities Kinetic heap Kinetic hanger, heater & tournament Dynamic convex hull
Lines

O(nlog2⁡n){displaystyle O(nlog ^{2}n)}

O(nlog2⁡n){displaystyle O(nlog ^{2}n)}

O(nlog⁡n){displaystyle O(nlog n)}

Line segments

O(mnlog32⁡n){displaystyle O(m{sqrt {n}}log ^{frac {3}{2}}n)}

O(mα(n)log2⁡n){displaystyle O(malpha (n)log ^{2}n)}

O(mlog⁡nlog⁡log⁡n){displaystyle O(mlog nlog log n)}

δ-intersecting curves

O(n2log⁡n){displaystyle O(n^{2}log n)}

O(λδ(n)log⁡n){displaystyle O(lambda _{delta }(n)log n)}

n/a

Here,

α(x){displaystyle alpha (x)}

denotes the inverse Ackermann function.

δ{displaystyle delta }

-intersecting curves refer to curves where each pair has at most

δ{displaystyle delta }

intersections, and

λδ(n){displaystyle lambda _{delta }(n)}

refers to a term in the Davenport-Schinzel sequence, which gives the maximum size of the upper envelope of

n{displaystyle n}

δ−{displaystyle delta -}

intersecting curves.

n{displaystyle n}

is the largest number of elements in the queue at any given time, while

m{displaystyle m}

refers to the total number of elements that are ever in the queue.

. . . Kinetic priority queue . . .

This article is issued from web site Wikipedia. The original article may be a bit shortened or modified. Some links may have been modified. The text is licensed under “Creative Commons – Attribution – Sharealike” [1] and some of the text can also be licensed under the terms of the “GNU Free Documentation License” [2]. Additional terms may apply for the media files. By using this site, you agree to our Legal pages . Web links: [1] [2]

. . . Kinetic priority queue . . .