Wikiszótár

elsőbbségi sor

Magyar

Kiejtés

  • IPA: [ ˈɛlʃøːpʃeːɡiʃor]

Főnév

elsőbbségi sor

  1. (matematika)

Az elsőbbségi sor (priority queue) egy speciális adatstruktúra, amelyben minden elemhez tartozik egy prioritás, és mindig a legnagyobb (vagy legkisebb, ha minimális prioritású a sor) prioritású elem kerül először kiszolgálásra. Ez különbözik a hagyományos soroktól, ahol az elemek érkezési sorrendben kerülnek kiszolgálásra (FIFO).


Tulajdonságai:

  • Az elemek rendezve vannak prioritás szerint.
  • Alapvető műveletek:
    1. Beszúrás (insert): Egy elem hozzáadása adott prioritással.
    2. Legnagyobb/legkisebb prioritású elem kivétele (extract-max vagy extract-min): A legnagyobb (max-prioritású sor) vagy legkisebb (min-prioritású sor) prioritású elem kivétele a sorból.
    3. Csúcs prioritású elem lekérdezése (peek vagy get-max/get-min): Megnézi a legnagyobb/legkisebb prioritású elemet anélkül, hogy eltávolítaná.


Implementációk:

Az elsőbbségi sort többféleképpen implementálhatjuk:

1. Lista vagy tömb:

  • A beszúrás egyszerűen hozzáfűzi az elemet a végére.
  • A kivétel előtt rendezni kell a listát.
  • Időbonyolultság:
    • Beszúrás: (O(1))
    • Kivétel: (O(n)) (ha rendezni kell).

2. Rendezett lista:

  • Az elemek mindig rendezetten vannak tartva.
  • Időbonyolultság:
    • Beszúrás: (O(n))
    • Kivétel: (O(1)).

3. Kétdimenziós tömb (hash):

  • Az elemek prioritás szerint csoportosítva vannak.
  • Kivétel és beszúrás gyors, de csak speciális esetekre alkalmas.

4. Heap (halom):

  • A leggyakoribb implementáció.
  • A halom egy részben rendezett bináris fa (általában bináris heap):
    • Max-heap: A szülőcsomópont értéke mindig nagyobb vagy egyenlő a gyerekek értékével.
    • Min-heap: A szülőcsomópont értéke mindig kisebb vagy egyenlő a gyerekek értékével.
  • Időbonyolultság:
    • Beszúrás: (O(n))
    • Kivétel: (O(n)).
  • Ez az implementáció gyakran használja tömbbel való reprezentációt.

5. Binomiális halom és Fibonacci halom:

  • Speciális változatok, amelyek a heapet optimalizálják bizonyos műveletekre.
  • Hatékonyabbak, ha sok egyesítési művelet szükséges (merge).


Felhasználási területek:

  1. Gráfalgoritmusok:
    • Dijkstra algoritmus (legkisebb út keresése).
    • Prim algoritmus (minimális feszítőfa keresése).
  2. Ütemezési problémák:
    • Operációs rendszerek folyamat- vagy szálütemezése.
  3. Adatfeldolgozás:
    • Tetszőleges nagy adatmennyiség szűrése és feldolgozása prioritások szerint.
  4. Egyéb problémák:
    • Játékokban ellenségek vagy események kezelése prioritások alapján.
    • Hátizsák-probléma bizonyos változatai.


Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=elsőbbségi_sor&oldid=3480199”