Elsőbbségi sor (programozás)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. március 25-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A  prioritási sor egy absztrakt adattípus a programozásban , amely két kötelező műveletet támogat - adjon hozzá egy elemet, és vegye ki a maximumot [1] (minimális). Feltételezzük, hogy minden elemhez ki lehet számítani a prioritását  - egy valós számot, vagy általános esetben egy lineárisan rendezett halmaz elemét [2] .

Leírás

A prioritási sor által megvalósított fő módszerek a következők [2] [3] [1] :

Ebben az esetben egy kisebb kulcsérték magasabb prioritásnak felel meg.

Bizonyos esetekben természetesebb, hogy a kulcs a prioritással együtt nő. Ekkor a második módszert nevezhetjük extract_maximum()[1] -nek .

Számos olyan implementáció létezik, amelyben mindkét alapművelet a legrosszabb esetben korlátozott időn belül történik (lásd "O" nagy és "o" kicsi ), ahol  a tárolt párok száma.

Példák

Példaként egy prioritási sorra vegye figyelembe a dolgozó feladatlistáját. Amikor befejez egy feladatot, áttér a következőre - a legmagasabb prioritásúra (a kulcs a prioritás reciprokja lesz) -, vagyis végrehajtja a maximum kivonásának műveletét. A főnök hozzáadja a feladatokat a listához, jelezve azok prioritását, azaz elvégzi az elem hozzáadásának műveletét.

Prioritási sorbővítmények

A gyakorlatban a prioritási sor interfészt gyakran kibővítik más műveletekkel [4] [3] :

Az indexelt prioritású sorokban (cím : [5] ) lehetőség van az elemekhez index szerint hozzáférni. Az ilyen sorok használhatók például több rendezett sorozat egyesítésére (multiway merge) [1] .

Szintén szóba jöhet a kétvégű prioritási sor (DEPQ ) ,  amelyben mind a minimális, mind a maximális elemhez vannak hozzáférési műveletek [6] .

Megvalósítások

A prioritási sor különféle adatstruktúrák alapján implementálható.

A legegyszerűbb (és nem túl hatékony) megvalósítások használhatnak rendezetlen vagy rendezett tömböt , linkelt listát , amely alkalmas kis sorokhoz. Ebben az esetben a számítások lehetnek „lusták” (a számítások súlyossága átkerül az elem kinyerésére), és korai (buzgó), amikor az elem beillesztése nehezebb, mint a kinyerése. Vagyis az egyik művelet időben végrehajtható , a másik pedig - legrosszabb esetben -re , ahol  a sor hossza [1] .

Hatékonyabbak a kupac alapú implementációk , ahol mindkét művelet a legrosszabb esetben is elvégezhető időben [1] . Ezek közé tartozik a bináris kupac , a binomiális kupac , a fibonacci kupac , a párosító kupac[6] .

A prioritási sor absztrakt adattípusa (ATD) a halom ADT-ből származik a megfelelő függvények átnevezésével. A minimális (maximális) érték mindig a kupac tetején van [7] .

Python példa

A Python szabványos könyvtára tartalmaz egy modult heapq[8] , amely egy prioritási sort [9] valósít meg :

# importáljon két sorfüggvényt a cikkben használt névvel a heapq -ből import heappush as insert , heappop as extract_maximum pq = [] # inicializálja a lista beszúrását ( pq , ( 4 , 0 , "p" )) # "p" elem beszúrása sorba " 0 indexű és 4 prioritású beszúrás ( pq , ( 2 , 1 , "e" )) beszúrás ( pq , ( 3 , 2 , "a" )) beszúrás ( pq , ( 1 , 3 , "h") )) # fontosságinövekvőelemetnégyakinyomtatja sorrendben _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Ez a példa a "heap" szót adja ki.

Jegyzetek

  1. ↑ 1 2 3 4 5 6 Sedgewick, Wayne, 2011 .
  2. ↑ 1 2 Aho, Hopcroft, Ullman, 2000 .
  3. ↑ 1 2 Kormen et al., 2005 .
  4. ↑ Robert Sedgewick. Algoritmusok C++ nyelven, 1–4. rész: Alapok, adatstruktúra, rendezés, keresés. - Harmadik kiadás. - Addison-Wesley Professional. — 752 p. - ISBN 978-0-7686-8533-6 .
  5. ↑ Mehlhorn, Sanders, 2008 .
  6. ↑ 1 2 Sahni, Mehta, 2018 .
  7. ↑ Rabhi, Lapalme, 1999 .
  8. ↑ 8.4. heapq - Heap queue algoritmus . Letöltve: 2014. november 25. Az eredetiből archiválva : 2017. december 4..
  9. ↑ David Beazley, Brian K. Jones. 1.5. Priority Queue megvalósítása // Python Cookbook. - 3. kiadás. - O'Reilly Media, Inc., 2013. - 706 p. — ISBN 978-1-4493-4037-7 .

Irodalom

  • Kormen, T., Leizerson, C., Rivest, R., Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M .: Williams , 2005. - 1296 p. — ISBN 5-8459-0857-4 .
  • Aho A. W., Hopcroft J. E., Ullman J. D. Data Structures and Algorithms. - Williams, 2000. - 384 p. — ISBN 9785845901224 . , 4.10. Elsőbbségi sorok
  • Robert Sedgewick; Kevin Wayne. 2.4 Elsőbbségi sorok // Algoritmusok. - Negyedik kiadás. - Addison-Wesley Professional, 2011. - 992 p. — ISBN 978-0-13-276257-1 .
  • Gerth Stølting Brodal, Chris Okasaki. Optimális tisztán funkcionális prioritású sorok  // BRICS jelentéssorozat. - Aarhusi Egyetem Számítástechnikai Tanszék, 1996. - RS-96-37 sz . — ISSN 0909-0878 .
  • Fethi Rabhi és Lapalme, G. Algorithms: A Functional Programming Approach . - Addison-Wesley, 1999. - P.  92-93 , 106-107. — 235 p. — ISBN 9780201596045 .
  • Sartaj Sahni és Dinesh P. Mehta. II. rész: Priority Queues // Adatstruktúrák és alkalmazások kézikönyve. — 2. kiadás. - Chapman és Hall / CRC, 2018. - 1100 p. — ISBN 9781498701853 .
  • Mehlhorn, Kurt, Sanders, Peter. 6. Prioritási sorok // Algoritmusok és adatstruktúrák: Az alapvető eszköztár. - Springer, 2008. - 300 p. — ISBN 978-3-540-77978-0 .

Linkek

  • Elsőbbségi sorok Ruby számára :
  • Coq által ellenőrzött Haskell prioritási sor megvalósítása :