Sor prioritás (programozás)
A sorban prioritás (angol prioritásos sor.) - egy absztrakt adattípus programozás. támogatja a két kötési műveletek - hozzáad egy elem, és a kivonat a maximális (minimális). Feltételezzük, hogy minden elem ki tudja számítani annak kiemelt - valós szám, vagy általában, egy elem a lineárisan rendezett halmaz.
Alapvető módszerek által végrehajtott prioritási sor, az alábbiak szerint:
- insert (kulcs, érték) - egészíti ki a páros (kulcs, érték) a tároló;
- extract_minimum () - visszaadja egy pár (kulcs, érték) minimum érték a kulcsot, és távolítsa el a tárolóból.
Így minimális kulcs érték megfelel a magasabb prioritást.
Egyes esetekben több természetes kulcsfontosságú növekedési együtt prioritás. Ezután a második módszer lehet nevezni extract_maximum ().
Számos megvalósítások, amelyekben a két alapvető műveletek elvégzésekor a legrosszabb esetben az időben által határolt O (log n) - száma tárolt párok.
Példaként a prioritási sor listáját megtekintheti a munkás feladatokat. Amikor befejezi egy feladatot, akkor továbblép a következő - a legmagasabb prioritású (a kulcs lesz a fordítottja prioritás) - azaz végzi működését kitermelése a maximum. Head hozzáteszi, hogy a feladatok listáját, feltüntetve azok prioritást, azaz végrehajtja a műveletet, hozzátéve az elem.
Extension összhangban az elsőbbségi jog
A gyakorlatban, a felület sorban kiemelten gyakran bővíteni egyéb műveletek:
- vissza a legkisebb elem kivétele nélkül a sorból
- prioritásának megváltoztatásához bármely elemének
- távolítson el minden eleme
- egyesíteni a két vonal egyetlen
Prioritású sorba lehet végrehajtani alapján a különböző adatszerkezeteket.
A legegyszerűbb (és nem túl hatékony) végrehajtására használhatja rendezetlen vagy rendezett tömböt. láncolt lista. alkalmas kis sorok. A számítások lehet, mint „lusta” (nehézség számítási alapegységhez át a extrakció) és a korai (szívesen), amikor a beilleszthető elem nehezebb eltávolítását. Azaz, az egyik a művelet elvégezhető O (1)
Hatékonyabb végrehajtása alapján a kupac. ahol mind műveletek végezhetők a legrosszabb esetben O (log N)
Absztrakt adattípus (ADT) a sorban prioritást kapott ADT kupac átnevezés a funkcióit. A minimális (maximális) értéke mindig az a kupac tetején.
Példa Edit Python
Python Standard Library tartalmaz heapq modult. egy sorban prioritást:
Ez a példa mutatja a szó «halom».