= Egyszerűsített kupacok =

Kulcsmódosítás nélküli, egyszerűsített kupac adatszerkezetek implementálása és alkalmazása a Dijkstra-algoritmusban. 

== Háttér ==

Sok algoritmus épül prioritásos sorok használatára, köztük az egyik legalapvetőbb gráfalgoritmus, a Dijkstra-algoritmus is. A prioritásos sort általában valamilyen [http://en.wikipedia.org/wiki/Heap_%28data_structure%29 kupac adatszerkezettel] valósítjuk meg (pl. a klasszikus [http://en.wikipedia.org/wiki/Binary_heap bináris kupaccal]). Fontos kérdés, hogy az alapvető műveletek (elem beszúrása, minimális kulcsú elem kivétele) mellett van-e lehetőség arra, hogy egy, már a kupacban lévő elem kulcsát csökkentsük. A Dijkstra-algoritmusban erre szükségünk van, de a szokásos implementáció (pl. amit a LEMON-ban található kupac struktúrákban is alkalmazunk) helyett egy másik lehetőség, hogy az érintett elemet beszúrjuk újra a kupacba a módosított, kisebb kulccsal. Kivételkor a legkisebb (legjobb) kulcsértékkel rendelkező előfordulását fogjuk először megkapni, a többi felesleges előfordulását pedig később könnyen kiszűrhetjük ha nyilvántartjuk, hogy mely elemeket vettük már ki a kupacból.

Ez a változat tulajdonképpen egy egyszerűsítést jelent, hiszen egyrészt kevesebb műveletet kell megvalósítanunk, másrészt pedig ezáltal elkerülhetjük, hogy a kupacban lévő elemekről tárolnunk kelljen az aktuális elhelyezkedésüket (a kulcscsökkentéshez erre szükségünk van, de a többi alapművelethez nincs). Így a beszúrás és törlés műveletek gyorsabbá válhatnak.

Mivel a gyakorlatban előforduló útvonalkeresések esetén kulcscsökkentésre tipikusan viszonylag ritkán van szükség, az egyszerűsített kupacok hatékonyabbak lehetnek. Több tanulmány is született, amely ezt támasztja alá, pl.
* [ftp://ftp.cs.utexas.edu/pub/techreports/honor_theses/cs-07-36-chen.pdf ​Mo Chen. Measuring and Improving the Performance of Cache-efficient Priority Queues in Dijkstra's Algorithm]
* [ftp://ftp.cs.utexas.edu/pub/techreports/tr07-54.pdf Mo Chen et. al. Priority Queues and Dijkstra's Algorithm]


== Feladat ==

A feladat néhány fontos kupac adatszerkezetből kulcscsökkentés nélküli változat implementálása, valamint a Dijkstra-algoritmusban mért hatékonyságuk alapos összehasonlító elemzése különböző gráfokon. Egy lehetséges folytatás további speciális kupac adatszerkezetek implementálása és összehasonlítása.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat.

'''Kapcsolódó ticketek:''' #381, #313.

== Előfeltételek ==

 - C++ programozási nyelv ismerete
 - alapvető gráfelméleti ismeretek 
 - angol nyelvismeret