„Kupac (adatszerkezet)” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
→Alkalmazása: clean up AWB |
|||
11. sor:
* Kiválasztó algoritmusokban a ''k''-adik legkisebb vagy legnagyobb elem megkeresése lineáris időben elvégezhető kupaccal.
* Súlyozott gráfokat bejáró algoritmusok gyorsíthatóak kupacok alkalmazásával (pl. [[Dijkstra-algoritmus]])
{{clear}}
== Műveletek kupacokban ==
37. sor:
* '''Beszúr''': Egy újabb kulcs beszúrása.
* '''Összefűz''': Két kupacot összefűz, mindkettő elemeit megtartva.
A min-kupacokon hasonló műveleteket értelmezünk; a maximumkeresés és -törlés helyett minimumkeresést és törlést, illetve a kulcsnövelés helyett kulcs-csökkentést.
A főbb kupactípusokban az egyes műveletek komplexitása max-kupac esetén (min-kupacban a megfelelő művelet komplexitása megegyezik) a jobb oldali táblázatban látható. A táblázatban O(f) esetén a lépésszám felülről becsülhető f konstansszorosával (lásd [[O jelölés]]), θ(f) esetén pedig a lépésszám pontosan f konstansszorosa.
| |||