Lista posortowana kinetycznie

Kinetyczna lista posortowana to kinetyczna struktura danych służąca do utrzymywania listy punktów w ruchu w posortowanej kolejności. Jest używany jako poprzednik kinetycznej struktury danych oraz jako składnik bardziej złożonych struktur danych kinetycznych, takich jak najbliższa para kinetyczna .

Realizacja

Ta struktura danych przechowuje listę elementów w posortowanej kolejności, z certyfikatami wymuszającymi kolejność między sąsiednimi elementami. Gdy certyfikat nie powiedzie się, odpowiednie elementy są zamieniane. Następnie należy zaktualizować co najwyżej trzy certyfikaty, certyfikat zamienionej pary oraz dwa certyfikaty obejmujące zamienione elementy i elementy posortowanej listy, które bezpośrednio poprzedzają i następują po zamienionej parze.

Na przykład, biorąc pod uwagę posortowaną listę {A,B,C,D,E,F}, certyfikaty będą miały postać [A

Analiza

Ta kinetyczna struktura danych to:

• Responsive : awaria certyfikatu powoduje jedną zamianę (co zajmuje czas O(1)) i zmiany certyfikatu O(1), których ponowne zaplanowanie zajmuje czas O(log n)
• Lokalny : każdy element jest zaangażowany w maksymalnie 2 certyfikaty
• Compact : jest dokładnie n -1 certyfikatów dla listy n elementów
• Wydajny : ta struktura danych nie powoduje żadnych zewnętrznych zdarzeń wewnętrznych , każda zmiana kolejności elementów powoduje dokładnie jeden błąd certyfikatu.

Uogólnienie

Tę strukturę danych można uogólnić do kinetycznej struktury danych, która może zwrócić posortowaną listę punktów w czasie i procesach ${\ Displaystyle O (n \ log m)}$${\ Displaystyle O ({\ frac {n ^ {2}} {m}})}$ suma zdarzeń, zakładając trajektorie pseudoalgebraiczne , gdzie ${\ displaystyle m}$ jest parametrem struktury danych. W ten sposób można dokonać kompromisu między czasem konserwacji a czasem zapytań, aby dostosować się do określonych aplikacji.

$danych$ punkty są dowolnie dzielone na m podzbiorów o rozmiarze w podzbiorach są utrzymywane listy posortowane $)$ podlista musi przetwarzać , ponieważ jest ${\ Displaystyle O (1)}$ zamiany każdego z ${\ Displaystyle O ({\ Frac {n ^ {2}} {m ^ {2}}})}$ par elementów. Zatem całkowity czas wymagany do utrzymania struktury danych wynosi ${\ Displaystyle O ({\ Frac {n ^ {2}} {m}})}$ . Żądania $połączenie$ posortowanej odpowiedzieć poprzez posortowanych list podrzędnych

• Abama, MA; De Berg, M. (2007), „Kinetic sorting and kinetic convex hulls”, Wydanie specjalne na dwudziestym pierwszym dorocznym sympozjum geometrii obliczeniowej - SoCG 2005, Geometria obliczeniowa: teoria i zastosowania , 37 (1): 16–26, doi : 10.1016/j.comgeo.2006.02.004 .