Prioritní fronta (programování)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. března 2021; kontroly vyžadují 2 úpravy .

Prioritní fronta je abstraktní datový typ v programování , který podporuje dvě povinné operace – přidat prvek a extrahovat maximum [  1] (minimum). Předpokládá se, že pro každý prvek je možné vypočítat jeho prioritu  - reálné číslo nebo v obecném případě prvek lineárně uspořádané množiny [2] .

Popis

Hlavní metody implementované prioritní frontou jsou následující [2] [3] [1] :

V tomto případě menší hodnota klíče odpovídá vyšší prioritě.

V některých případech je přirozenější, že klíč roste spolu s prioritou. Pak lze druhou metodu nazvat extract_maximum()[1] .

Existuje řada implementací, ve kterých se obě základní operace provádějí v nejhorším případě v omezeném čase (viz "O" velké a "o" malé ), kde  je počet uložených párů.

Příklady

Jako příklad prioritní fronty zvažte seznam úkolů pracovníka. Když dokončí jeden úkol, přejde na další - nejvyšší prioritu (klíč bude převrácená hodnota priority) - to znamená, že provede operaci vytěžení maxima. Šéf přidá úkoly do seznamu s uvedením jejich priority, to znamená, že provede operaci přidání prvku.

Prioritní rozšíření fronty

V praxi je rozhraní prioritní fronty často rozšířeno o další operace [4] [3] :

V indexovaných prioritních frontách (adresovaných [5] ) je možné přistupovat k prvkům podle indexu. Takové fronty lze použít například ke sloučení několika seřazených sekvencí (multiway merge) [1] .

V úvahu připadá i fronta s dvojitou prioritou ( DEPQ ) , ve  které jsou přístupové operace jak k minimálnímu, tak k maximálnímu prvku [6] .

Implementace

Prioritní fronta může být implementována na základě různých datových struktur.

Nejjednodušší (a nepříliš efektivní) implementace mohou používat neuspořádané nebo uspořádané pole , propojený seznam , vhodné pro malé fronty. V tomto případě mohou být výpočty buď „líné“ (závažnost výpočtů se přenáší na extrakci prvku), nebo rané (horlivé), kdy je vložení prvku obtížnější než jeho extrakce. To znamená, že jedna z operací může být provedena v čase , a druhá - v nejhorším případě pro , kde  je délka fronty [1] .

Efektivnější jsou implementace založené na haldě , kde lze obě operace provést v nejhorším případě včas [1] . Patří sem binární halda , binomická halda , Fibonacciho halda , párovací halda[6] .

Abstraktní datový typ (ATD) pro prioritní frontu je odvozen z haldy ADT přejmenováním odpovídajících funkcí. Minimální (maximální) hodnota je vždy v horní části haldy [7] .

Příklad Pythonu

Standardní knihovna Pythonu obsahuje modul heapq[8] , který implementuje prioritní frontu [9] :

# import dvou funkcí fronty s názvy použitými v tomto článku z heapq import heappush jako insert , heappop jako extract_maximum pq = [] # inicializace vložení seznamu ( pq , ( 4 , 0 , "p" )) # vložení prvku "p" do fronty " s indexem 0 a prioritou 4 vložit ( pq , ( 2 , 1 , "e" )) vložit ( pq , ( 3 , 2 , "a" )) vložit ( pq , ( 1 , 3 , "h" )) # prioritypořadívzestupnémveprvkyčtyřivytiskněte _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Tento příklad vypíše slovo "halda".

Poznámky

  1. ↑ 1 2 3 4 5 6 Sedgewick, Wayne, 2011 .
  2. ↑ 1 2 Aho, Hopcroft, Ullman, 2000 .
  3. ↑ 1 2 Kormen a kol., 2005 .
  4. ↑ Robert Sedgewick. Algoritmy v C++, Části 1–4: Základy, Struktura dat, Třídění, Vyhledávání. - Třetí edice. — Addison-Wesley Professional. — 752 s. - ISBN 978-0-7686-8533-6 .
  5. ↑ Mehlhorn, Sanders, 2008 .
  6. ↑ 1 2 Sahni, Mehta, 2018 .
  7. ↑ Rabhi, Lapalme, 1999 .
  8. ↑ 8.4. heapq - Algoritmus fronty haldy . Získáno 25. listopadu 2014. Archivováno z originálu 4. prosince 2017.
  9. ↑ David Beazley, Brian K. Jones. 1.5. Implementace prioritní fronty // Python Cookbook. - 3. vydání. - O'Reilly Media, Inc., 2013. - 706 s. — ISBN 978-1-4493-4037-7 .

Literatura

  • Kormen, T., Leizerson, C., Rivest, R., Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M .: Williams , 2005. - 1296 s. — ISBN 5-8459-0857-4 .
  • Aho A. W., Hopcroft J. E., Ullman J. D. Data Structures and Algorithms. - Williams, 2000. - 384 s. — ISBN 9785845901224 . , 4.10. Prioritní fronty
  • Robert Sedgewick; Kevin Wayne. 2.4 Prioritní fronty // Algoritmy. — Čtvrté vydání. - Addison-Wesley Professional, 2011. - 992 s. — ISBN 978-0-13-276257-1 .
  • Gerth Stølting Brodal, Chris Okasaki. Optimální, čistě funkční prioritní fronty  // Série zpráv BRICS. - Katedra informatiky University of Aarhus, 1996. - č. RS-96-37 . — ISSN 0909-0878 .
  • Fethi Rabhi a Lapalme, G. Algorithms: A Functional Programming Approach . - Addison-Wesley, 1999. - S.  92-93 , 106-107. — 235p. — ISBN 9780201596045 .
  • Sartaj Sahni a Dinesh P. Mehta. Část II: Prioritní fronty // Příručka datových struktur a aplikací. — 2. vyd. - Chapman a Hall / CRC, 2018. - 1100 s. — ISBN 9781498701853 .
  • Mehlhorn, Kurt, Sanders, Peter. 6. Prioritní fronty // Algoritmy a datové struktury: Základní sada nástrojů. - Springer, 2008. - 300 s. — ISBN 978-3-540-77978-0 .

Odkazy

  • Prioritní fronty pro Ruby :
  • Implementace prioritní fronty Haskell ověřená Coq :