prioritás Queuing
osztály sor
Kiegyensúlyozott bináris fa segítségével gyorsan megtalálja minden oldalon. Azonban sok alkalmazás igényli nem kap egy tetszőleges csomópont, és csak minimális. Ez a probléma, például a szervezet irányított keresést. Egy alkalmas adatstruktúrát ez lesz sorban kiemelt (prioritási sort).
Mielőtt rátérnénk a részleteket a szervezet a prioritási sor, adunk egy példát a használatát (queue.js modulus): Ebben a példában a prioritási sor 50 kerül sor véletlenszerű számok 0-tól 99 Ezután egy hurkot, míg az elemeket kivenni a sorból, hogy az egyre nagyobb érték :
Amellett, hogy a kivitelező, az osztály Sor 3 alapvető funkciója van: unshift (n) - hozzáadásával az összes új elem n (mozgó „back” nagy elemek), shift () - nyomja a minimális elem (változó minden „előre”), és végül, a logikai függvény üres () értéke igaz. ha a várólista üres (egyébként - hamis).
Ön tudja menteni a prioritási sor nem csak egy szám vagy egy karakterlánc, hanem semmilyen tárgyat. Ehhez felül kell bírálni a funkció kevesebb, mint:
Szervezet fák
Rendelje meg a prioritási sor csomópont egy bináris fa. Ez a fa két gyerek minden egyes csomópont nagyobbnak kell lennie, vagy egyenlő, mint a szülő csomópont. Ennek megfelelően a gyökér a fa a legkisebb egység. Ez a szervezet a prioritási sor az úgynevezett bináris kupac. Az alábbiakban a fák véletlen számokat az első példa az előző részben:
A fa csomópontjait fogják tárolni a tömbben ar. A gyökér csomópont ar elem [1]. Két leszármazottai a ar [2], és Ar [3]. Leszármazottai i -edik csomópont (elem ar [i]) tárolja a ar [2 * i] és Ar [2 * i + 1]. Ezzel szervezet adatai, bináris fa kiegyensúlyozott. Ha a csomópontok száma egyenlő a hossz = 2 k -1. A fa lesz elfoglalva a levelek alsó (k -ik) szintet. Általában, az alsó szinten a fa van töltve balról jobbra, és a ar [hossza] a jobb szélső alsó szintű csomópont. Ar nulla tömbelem nem használják. Az alábbiakban egy bináris fa és annak megfelelő képviselet formájában egy tömb (vegye figyelembe, hogy az elemek a tömbben vannak a fa bejárás érdekében fentről lefelé és balról jobbra):
Hozzáadása elemet a sorhoz
Hozzáadása - egy viszonylag egyszerű művelet. Az új csomópont a fa először kerül a legalján azt. Ehhez egyszerűen helyezze egy új csomópont az utolsó csomópont a array (első sorban a funkció). Emlékezzünk, hogy ha a ++ előtt áll egy változó, először eggyel megnöveljük (lent, ez növeli a csomópontok száma ++ this.length fa), majd részt vesz a kifejezés: az utolsó elem a tömb, a csomópont lesz a gyermek csomópont egy index hossza / 2 === i >> 1 ( "osztás"). Ezután meg kell felemelni a fa gyökér (felcserélésével szülő csomópont helyekre), amíg ez kisebb, mint a szülő. A művelet kevesebb, mint az alapértelmezett funkció használható: egy permutációs függvény az i-edik és a j-edik eleme a tömb Ar jelentése a következő:
Az alábbiakban szekvenciális lépéseket, hogy egy új csomópont értéke 2, és felemelve a kijelölt helyet érte:
Popping egy elemet a sorból
Kiveheti a minimális elem a sorból, tegye a következőket. Első csere a gyökér és az utolsó csomópont a fa. Ezt követően, a korábbi gyökér (minimum egység) könnyen eltávolítható azáltal, hogy csökkenti a csomópontok száma length--. Azonban a korábbi utolsó csomópont, alapjaiban sérti a tulajdonságait a fa. Ezért kell leereszteni, változó helyeken utódaik, míg ő nem fog „megfelelő” helyzetben a fán. Ez akkor történik, amikor annak a gyermek lesz nagyobb vagy egyenlő kihagyás csomópontot. Süllyesztés közben, a csomópont változások minimum két gyermek, nőtt a fenti minimális értéket. Az alábbiakban egy példát, amelyben leereszkedik gomb 5 csere után root 1:
Megfelelő kódot váltás funkció: Használja a „rendrakás” a fa, kezdve a csomópont csomópont és az alábbiakban:
Egy bináris kupac - a legegyszerűbb módja, hogy szervezzen egy sornak. Hogy támogassa a halom tulajdonságait behelyezésekor vagy toló csomópont igényel egy átlagos log2 N műveletek, ahol N - a csomópontok száma a fában. Rovására néhány komplikáció, akkor lehetséges egység bonyolultsága O (1) hozzáadásával (azaz, az adagolást olyan ütemben nem függ a csomópontok száma). Ez megőrzi a logaritmikus komplexitása csomópont eltávolítását. A megfelelő adatok szerkezet az úgynevezett egy halom Fibonacci.
Megjegyezzük, hogy a prioritási sor egyidejűleg egy módja válogatás (egyes értékrend elhelyezni a sorban, ahol már eltávolította a megadott sorrendben).