Prioritetskö (programmering)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 mars 2021; kontroller kräver 2 redigeringar .

En  prioritetskö är en abstrakt datatyp i programmering som stöder två obligatoriska operationer - lägg till ett element och extrahera maximalt [1] (minimum). Det antas att det för varje element är möjligt att beräkna dess prioritet  - ett reellt tal eller, i det allmänna fallet, ett element i en linjärt ordnad mängd [2] .

Beskrivning

De huvudsakliga metoderna som implementeras av prioritetskön är följande [2] [3] [1] :

I detta fall motsvarar ett mindre nyckelvärde en högre prioritet.

I vissa fall är det mer naturligt att nyckeln växer tillsammans med prioriteringen. Då kan den andra metoden kallas extract_maximum()[1] .

Det finns ett antal implementeringar där båda grundläggande operationerna utförs i värsta fall under begränsad tid (se "O" stor och "o" liten ), där  är antalet lagrade par.

Exempel

Som ett exempel på en prioriterad kö, betrakta en arbetares uppgiftslista. När han är klar med en uppgift går han vidare till nästa - högsta prioritet (nyckeln kommer att vara den ömsesidiga prioriteten) - det vill säga han utför operationen att extrahera det maximala. Chefen lägger till uppgifter i listan, anger deras prioritet, det vill säga utför operationen att lägga till ett element.

Förlängningar av prioriterade köer

I praktiken utökas ofta prioritetskögränssnittet med andra operationer [4] [3] :

I indexerade prioritetsköer (adresserade [5] ) är det möjligt att komma åt element via index. Sådana köer kan till exempel användas för att slå samman flera sorterade sekvenser (multiway merge) [1] .

Dubbeländad prioritetskö (DEPQ ) kan också övervägas ,  där det finns åtkomstoperationer till både minimum- och maximumelementet [6] .

Implementeringar

Prioritetskön kan implementeras baserat på olika datastrukturer.

De enklaste (och inte särskilt effektiva) implementeringarna kan använda en oordnad eller ordnad array , en länkad lista , lämplig för små köer. I det här fallet kan beräkningarna vara antingen "lata" (allvarligheten av beräkningarna överförs till utvinningen av elementet) och tidigt (ivrig), när införandet av elementet är svårare än dess utvinning. Det vill säga att en av operationerna kan utföras i tid och den andra - i värsta fall för , var  är kölängden [1] .

Mer effektiva är heap -baserade implementeringar , där båda operationerna kan utföras i värsta fall i tid [1] . Dessa inkluderar binär heap , binomial heap , fibonacci heap , parningshög[6] .

Den abstrakta datatypen (ATD) för prioritetskön härleds från heap-ADT genom att byta namn på motsvarande funktioner. Minsta (högsta) värde är alltid överst på högen [7] .

Python-exempel

Python-standardbiblioteket innehåller en modul heapq[8] som implementerar en prioritetskö [9] :

# importera två köfunktioner med namnen som används i den här artikeln från heapq import heappush som infoga , heappop som extrakt_maximum pq = [] # initiera listan infogning ( pq , ( 4 , 0 , "p" )) # infoga element "p" in i kön " med index 0 och prioritet 4 infoga ( pq , ( 2 , 1 , "e" )) infoga ( pq , ( 3 , 2 , "a" )) infoga ( pq , ( 1 , 3 , "h" )) # prioritetsordningstigandeielementenfyradeutskriv _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Detta exempel kommer att mata ut ordet "hög".

Anteckningar

  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. Algoritmer i C++, del 1–4: Grundläggande, datastruktur, sortering, sökning. - Tredje upplagan. — Addison-Wesley Professional. — 752 sid. - 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-köalgoritm . Hämtad 25 november 2014. Arkiverad från originalet 4 december 2017.
  9. ↑ David Beazley, Brian K. Jones. 1.5. Implementera en prioriterad kö // Python Cookbook. - 3:e upplagan. - O'Reilly Media, Inc., 2013. - 706 sid. — ISBN 978-1-4493-4037-7 .

Litteratur

  • Kormen, T., Leizerson, C., Rivest, R., Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a upplagan - M . : Williams , 2005. - 1296 sid. — ISBN 5-8459-0857-4 .
  • Aho A. W., Hopcroft J. E., Ullman J. D. Data Structures and Algorithms. - Williams, 2000. - 384 sid. — ISBN 9785845901224 . 4,10 . Prioriterade köer
  • Robert Sedgewick; Kevin Wayne. 2.4 Prioritetsköer // Algoritmer. - Fjärde upplagan. - Addison-Wesley Professional, 2011. - 992 sid. — ISBN 978-0-13-276257-1 .
  • Gerth Stølting Brodal, Chris Okasaki. Optimala Rent funktionella prioritetsköer  // BRICS Report Series. - Institutionen för datavetenskap Universitetet i Aarhus, 1996. - Nr RS-96-37 . — ISSN 0909-0878 .
  • Fethi Rabhi och Lapalme, G. Algoritmer: En funktionell programmeringsmetod . - Addison-Wesley, 1999. - P.  92-93 , 106-107. — 235 sid. — ISBN 9780201596045 .
  • Sartaj Sahni och Dinesh P. Mehta. Del II: Prioriterade köer // Handbook of Data Structures and Applications. — 2:a uppl. - Chapman och Hall / CRC, 2018. - 1100 sid. — ISBN 9781498701853 .
  • Mehlhorn, Kurt, Sanders, Peter. 6. Prioritetsköer // Algoritmer och datastrukturer: Den grundläggande verktygslådan. - Springer, 2008. - 300 sid. — ISBN 978-3-540-77978-0 .

Länkar

  • Prioriterade köer för Ruby :
  • Coq -verifierad Haskell prioritetsköimplementering :