Kinetický seřazený seznam - Kinetic sorted list

A kinetický seřazený seznam je kinetická datová struktura pro udržování a seznam bodů v pohybu v seřazeném pořadí. Používá se jako kinetická datová struktura předchůdce a jako součást složitějších kinetických datových struktur, jako je kinetický nejbližší pár.

Implementace

Tato datová struktura udržuje seznam prvků v seřazeném pořadí, přičemž certifikáty vynucují pořadí mezi sousedními prvky. Když certifikát selže, příslušné prvky jsou vyměněny. Poté musí být aktualizovány nejvýše tři certifikáty, certifikát vyměněného páru a dva certifikáty zahrnující vyměněné prvky a prvky seřazeného seznamu, které přímo předcházejí a sledují vyměněný pár.

Například vzhledem k seřazenému seznamu {A, B, C, D, E, F} budou certifikáty [A

Analýza

Tato kinetická datová struktura je:

• Reagovat: selhání certifikátu způsobí jednu výměnu (která trvá O (1) čas) a O (1) změny certifikátu, které přeplánují čas O (log n)
• Místní: každý prvek je zapojen maximálně do 2 certifikátů
• Kompaktní: existují přesně n-1 certifikáty pro seznam n elementy
• Účinný: tato datová struktura nezpůsobuje nic cizího interní události, každá změna v pořadí prvků způsobí právě jedno selhání certifikátu.

Zobecnění

Tuto datovou strukturu lze zobecnit na kinetickou datovou strukturu, která může vrátit seřazený seznam bodů ${ displaystyle O (n log m)}$ čas a procesy ${ displaystyle O ({ frac {n ^ {2}} {m}})}$ události celkem, za předpokladu pseudoalgebraický trajektorie, kde ${ displaystyle m}$ je parametr datové struktury. Lze tedy provést kompromis mezi časem údržby a dotazem a časem pro vyladění konkrétních aplikací.

V generalizované datové struktuře jsou body libovolně rozděleny do m podmnožin velikosti ${ displaystyle O ({ frac {n} {m}})}$a kinetické seřazené seznamy jsou udržovány v podmnožinách. Každý seřazený podlist musí být zpracován ${ displaystyle O ({ frac {n ^ {2}} {m ^ {2}}})}$ událostí (selhání certifikátu) maximum, protože existuje ${ displaystyle O (1)}$ swapy každého z ${ displaystyle O ({ frac {n ^ {2}} {m ^ {2}}})}$ dvojice prvků. Celková doba potřebná k udržení datové struktury je tedy ${ displaystyle O ({ frac {n ^ {2}} {m}})}$. Na žádosti o seřazený seznam lze poté odpovědět ${ displaystyle O (n log m)}$ sloučením seřazených sublistů s Sloučit třídění.

Reference

• Abam, M. A.; De Berg, M. (2007), „Kinetické třídění a kinetické konvexní slupky“, zvláštní vydání k dvacátému prvnímu ročníku Sympózium o výpočetní geometrii - SoCG 2005, Výpočetní geometrie: Teorie a aplikace, 37 (1): 16–26, doi:10.1016 / j.comgeo.2006.02.004.