Monotónní prioritní fronta - Monotone priority queue

v počítačová věda, a monotónní prioritní fronta je varianta prioritní fronta abstraktní datový typ ve kterém jsou priority vytěžených položek vyžadovány k vytvoření a monotónní sekvence. To znamená, že pro prioritní frontu, ve které je každá postupně extrahovaná položka ta s minimální prioritou (min. Halda), by měla být minimální priorita monotónně rostoucí. Naopak pro maximální hromadu by měla být maximální priorita monotónně klesající. Předpoklad monotónnosti vzniká přirozeně v několika aplikacích prioritních front a lze jej použít jako zjednodušující předpoklad k urychlení určitých typů prioritních front.^[1]:128

Nezbytnou a dostatečnou podmínkou ve frontě priorit monotónní je, že se člověk nikdy nepokusí přidat prvek s nižší prioritou než ta, která byla naposledy extrahována.

Aplikace

Monotónní prioritní fronty vznikají přirozeně při uspořádání událostí podle času, například sítě časové limity nebo diskrétní simulace událostí. Událost může způsobit, že bude v budoucnu naplánována nějaká akce, ale (skutečná nebo simulovaná) kauzalita činí pokusy o plánování akcí v minulosti nesmyslné.

v Dijkstrův algoritmus pro problém s nejkratší cestou, vrcholy daného váženého grafu jsou extrahovány ve vzestupném pořadí podle jejich vzdálenosti od počátečního vrcholu a k určení nejbližšího zbývajícího vrcholu k počátečnímu vrcholu je použita prioritní fronta. Proto jsou v této aplikaci operace prioritní fronty monotónní.

Podobně v algoritmy zametání v výpočetní geometrie `` Události, při kterých křivka protne bod zájmu, jsou upřednostněny souřadnicí zkříženého bodu a tyto události jsou extrahovány v monotónním pořadí. nejlepší první verze větev a svázaný.^[1]:128

Datové struktury

Libovolná prioritní fronta, která dokáže zpracovat jiné než monotónní extrakční operace, může také zpracovat monotónní extrakce, ale některé prioritní fronty se specializují na práci pouze pro monotónní extrakce nebo fungují lépe, když jsou extrakty monotónní. fronta na kbelík je jednoduchá datová struktura fronty priorit sestávající z pole indexovaného podle priority, kde každá buňka pole obsahuje a Kbelík položek s touto prioritou. Operace extrakce provádí a sekvenční vyhledávání pro první neprázdný kbelík a vybere libovolnou položku v tomto kbelíku. U extrakcí jiných než monotónních vyžaduje každá operace extrakce min čas (v nejhorším případě) úměrný délce pole (počtu odlišných priorit). Pokud je však použita jako fronta priorit monotónní, hledání další neprázdné kbelík může začít na prioritě poslední předchozí operace min. extraktu, nikoli na začátku pole. Tato optimalizace způsobí, že celkový čas pro sekvenci operací bude proporcionální k součtu počtu operací a délce pole, spíše než (jako v non-monotónním případě) součin těchto dvou veličin.^[2]

Cherkassky, Goldberg & Silverstein (1999) popsat složitější schéma zvané a Fronta haldy nahoře (HOT) pro monotónní prioritní fronty s celočíselnými prioritami, založené na víceúrovňovém bucketingu společně s konvenční prioritní frontou haldy. Pomocí této metody získají strukturu, která dokáže udržovat položky s celočíselnými prioritami v rozsahu od 0 k parametru C. Horká fronta používá konstantní čas na operaci vložení nebo snížení priority a amortizovaný čas ${ displaystyle O (( log C) ^ {1/3} ( log log C) ^ {1/2})}$ na operaci min.^[3] Další související struktura Raman (1996) umožňuje, aby prioritami byla celá čísla stroje, a opět umožňuje operace vložení a snížení priority s konstantním časem, s operacemi min. extraktu na prioritní frontě n položky s amortizovaným časem ${ displaystyle O ({ sqrt { log n log log n}})}$.^[4]Tyto výsledky vedou k odpovídajícímu zrychlení Dijkstrova algoritmu pro grafy s celočíselnými hranovými vahami.

Reference