„Kupacrendezés” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Nincs szerkesztési összefoglaló |
|||
| 16. sor: | 16. sor: | ||
* Az összefésülő rendezés stabil rendezés. |
* Az összefésülő rendezés stabil rendezés. |
||
* Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható. |
* Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható. |
||
==Forrás== |
|||
{{források}} |
|||
{{nincs forrás}} |
|||
==Kiegészítő irodalom== |
|||
*{{Cite book |
|||
| author= T. H. Cormen |
|||
| coauthors = C. E. Leiserson, R. L. Rivest |
|||
|title=Algoritmusok |
|||
|publisher=Műszaki Könyvkiadó |
|||
|location=Budapest |
|||
|year = 1999 |
|||
}} |
|||
* {{Cite book |
|||
| publisher = Princeton University |
|||
| url= http://www.cs.princeton.edu/~wayne/cs423/lectures/heaps-4up.pdf |
|||
|year = 2002 |
|||
| title = Binary and Binomial Heaps |
|||
}} |
|||
* {{Cite book |
|||
| publisher = mobiDIÁK könyvtár |
|||
| title = mobiDIÁK könyvtár |
|||
| chapter = Informatikai algoritmusok. Szakmai segédanyag programtervező matematikusok részére |
|||
| location = Debreceni Egyetem Informatikai Kar |
|||
| year = 2006 |
|||
| url = http://www.inf.unideb.hu/~aszalos/dn/alg/bin.pdf |
|||
}} |
|||
* {{Cite book|author= Ronald L. Rivest|coauthors= Charles E. Leiserson; Thomas H. Cormen|title=Algoritmusok | publisher=Műszaki Könyvkiadó Kft. |year=2001|isbn= 9789631630299}} |
|||
* {{Cite book| author = Thomas H. Cormen| coauthors = Charles E. Leiserson - Ronald L. Rivest - Clifford Stein|title = Új algoritmusok |publisher = SCOLAR KFT|isbn = 9789639193901 |year =2003 }} |
|||
[[Kategória:Rendezési algoritmusok]] |
[[Kategória:Rendezési algoritmusok]] |
||
A lap 2010. február 14., 02:27-kori változata
 |
Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. |
A kupacrendezés összehasonlító rendezési algoritmus, és a kiválasztó rendezések családjába tartozik. Helyben rendező, nem stabil rendezés.
A kupacrendezés a használt adatszerkezetről kapta a nevét, a kupacról. A kupacrendezés működése során előbb felépíti a kupacot, majd egyesével kiemeli a gyökérelemet, ami a kupac definíciója miatt a legnagyobb/legkisebb elem lesz.
Áttekintés
A kupacrendezés nevének megfelelően egy kupac felépítésével kezdődik. Az adatok felhasználásával létrehozunk egy kupacot, majd eltávolítjuk a legnagyobb elemet. A gyökérelem törlésével elromlott a kupac tulajdonság, ezt helyre kell állítanunk. Az elem törlése lehetséges úgy is, hogy a kupac legalsó szintjének jobb szélső elemével cserélünk, és az új jobb szélső elemet nem tekintjük a kupac részének. A helyreállítás úgy lehetséges, hogy az eredeti jobb szélső elemet a gyökérbe helyezzük, majd süllyesztjük. Az utóbbi változatban ez megegyezik a gyökérelem süllyesztésével. A süllyesztés a szülő elemet mindig a nagyobbik, illetve a jobb oldali gyerekkel cseréli, ha van ilyen, és nagyobb a szülőnél. Az algoritmus ezután mindig eltávolítja a következő legnagyobb, azaz a gyökérben található elemet, és helyreállítja a kupac tulajdonságot. Ha a kupacrendezés helyesen, tömbbel kerül implementálásra, és a jobb szélső elemmel való törlést választjuk, a tömb rendezett lesz, és nincs szükség az eredeti tömbnél több memóriára.
A kupac tulajdonság feltételezi, hogy minden szülő elem nagyobb, vagy azonos értékű, mint gyerekei. Ennek megfordításával minimális gyökerű kupacot kapunk, és csökkenően rendezett tömböt készíthetünk a fenti algoritmussal.
Összehasonlítás más rendezésekkel
A kupacrendezés a gyorsrendezéshez hasonló hatékonysággal rendelkezik. A gyorsrendezés általában valamivel gyorsabb, viszont legrosszabb esetben futásideje elérheti a Θ(n2) nagyságrendet. Bizonyos adatmennyiség felett a négyzetes futásidő elfogadhatatlan, a gyorsrendezés implementációjának ismeretében pedig könnyen elérhető, ezzel csökkentve az algoritmus biztonságát. Mivel a kupacrendezés nagyságrendje Θ(n log n) marad, jellemzően ezt az algoritmust választják a gyorsrendezéssel szemben azokban a rendszerekben, ahol a biztonság meghatározó tényező.
A kupacrendezés szembeállítható az összefésülő rendezéssel is. Időigényük hasonló, memóriaigényben az összefésülő rendezés rosszabbul állhat. Az összefésülő rendezés rendelkezik néhány előnnyel a kupacrendezéshez képest:
- Az összefésülő rendezés stabil rendezés.
- Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható.
Forrás
 |
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
Kiegészítő irodalom
- T. H. Cormen, C. E. Leiserson, R. L. Rivest. Algoritmusok. Budapest: Műszaki Könyvkiadó (1999)
- Binary and Binomial Heaps. Princeton University (2002)
- Informatikai algoritmusok. Szakmai segédanyag programtervező matematikusok részére, mobiDIÁK könyvtár. Debreceni Egyetem Informatikai Kar: mobiDIÁK könyvtár (2006)
- Ronald L. Rivest, Charles E. Leiserson; Thomas H. Cormen. Algoritmusok. Műszaki Könyvkiadó Kft. (2001). ISBN 9789631630299
- Thomas H. Cormen, Charles E. Leiserson - Ronald L. Rivest - Clifford Stein. Új algoritmusok. SCOLAR KFT (2003). ISBN 9789639193901