Kupac (adatstruktúra)

A számítástechnikában a kupac egy speciális fa típusú adatstruktúra , amely kielégíti a kupac tulajdonságot: ha B az A csomópont gyermekcsomópontja , akkor kulcs( A ) ≥ kulcs( B ). Ebből következik, hogy a legnagyobb kulcsú elem mindig a kupac gyökércsomópontja, ezért néha az ilyen kupacokat max-halomnak nevezik (vagy ha az összehasonlítás megfordul, mindig a legkisebb elem lesz a gyökércsomópont, az ilyen kupacokat ún. min-halmok ). Nincs korlátozás arra vonatkozóan, hogy az egyes kupaccsomópontok hány gyermekcsomóponttal rendelkeznek, bár a gyakorlatban ez a szám általában nem több, mint kettő. A kupac a prioritási sornak nevezett absztrakt adattípus leghatékonyabb megvalósítása . A halmok kulcsfontosságúak néhány hatékony gráfalgoritmusban , például Dijkstra algoritmusában a d-halmok és a heapsort esetében .  

A kupac adatszerkezetet nem szabad összetéveszteni a kupac fogalmával a dinamikus memóriafoglalásban . A kifejezést először kifejezetten adatstruktúrákra használták. Egyes korai népszerű programozási nyelvek, mint például a LISP , dinamikus memóriaelosztást biztosítottak a "kupac" adatstruktúra segítségével, amely a lefoglalt memóriamennyiség nevét adta. [1] .

A kupacokat általában tömbként valósítják meg, így nincs szükség mutatókra az elemei között.

A következő műveleteket általában a kupacokon hajtják végre:

• keresse meg a maximumot vagy keresse meg a minimumot : keresse meg a maximális elemet a max-halomban vagy a minimális elemet a min-halomban, ill.
• távolítsa el a max -ot vagy távolítsa el a min : távolítsa el a gyökércsomópontot a max- vagy min-halomban
• növelő vagy csökkentő kulcs : frissítési kulcs max- vagy min-halomban
• add : Új kulcs hozzáadása a kupachoz.
• egyesítése : két kupac összekapcsolása új kupac létrehozásához, amely mindkét eredeti összes elemét tartalmazza.

Opciók

• 2-3 kupac
• kétszülős kupac
• bináris kupac
• binomiális kupac
• Brodal sorban
• Halom D gyerekkel
• fibonacci kupac
• Halom bal szélső prioritással
• Iker kupac
• aszimmetrikus kupac
• puha halom
• hármas halom
• karteziánus fa

A változatok elméleti becsléseinek összehasonlítása

Az alábbiakban becslések találhatók a számítások időbeli összetettségére vonatkozóan bizonyos típusú kupacokon végzett műveleteknél. [1] Ahol egy érték csillaggal van megjelölve, a becslés amortizációs elemzésen (legrosszabb idő) alapul, ellenkező esetben a becslés a szokásos legrosszabb eset. O(F) aszimptotikus felső korlátot ad, Θ(F) pedig aszimptotikusan pontos becslést (lásd az "O" nagy és az "o" kicsi jelölést ). A műveletnevek a min-halomhoz vannak kiválasztva.

(*) Amortizációs idő
(**) Ahol n a legnagyobb kupac mérete

Ne feledje, hogy a "Brodal's queue" egy párhuzamos prioritási sor megvalósítása, amelyet egy Gert Brodal vezette csoport fejlesztett ki. [3]

Alkalmazás

A kupac adatstruktúráknak számos felhasználási módja van.

• Heapsort : Az egyik legjobb használt rendezési módszer, amely nem rendelkezik másodfokú legrosszabb forgatókönyvekkel.
• Keresési algoritmusok: Ha kupacot használunk, a minimum, maximum, mindkettő, a medián vagy a k . legnagyobb elem keresése történhet lineáris időben (gyakran akár állandó időben is). [négy]
• Grafikonalgoritmusok : Ha a kupacot adatstruktúraként használjuk a belső bejáráshoz, a futásidő polinomiális sorrendben csökken. Ilyen problémák például a Prim minimális feszítőfa-konstrukciós algoritmusa és a Dijkstra legrövidebb út problémája .

Egy teljes és majdnem teljes bináris kupac nagyon hatékonyan ábrázolható egy indextömb segítségével . Az első (vagy utolsó) elem tartalmazza a gyökért. A tömb következő két eleme tartalmazza a gyökér gyermekcsomópontjait. A következő négy elem két csomópontból négy gyermeket tartalmaz, amelyek a gyökér gyermekei, és így tovább. Így a szintcsomópont gyermekei a npozíciókban 2nés 2n+1az egyből indexelt tömbnél, vagy a pozíciókban 2n+1és 2n+2egy indexelt tömbnél helyezkednek el. nulláról. Ez lehetővé teszi, hogy felfelé vagy lefelé mozogjon a fában egyszerű tömbindex számítások elvégzésével. A halomkiegyenlítés a nem megfelelő elemek átrendezésével történik. Mivel a kupacot extra memóriával nem rendelkező tömbből építhetjük fel (például csomópontokhoz), a heapsort segítségével rendezhetjük a tömböt a helyére.

Megvalósítások

• A C++ Standard Template Library függvénysablonokat biztosít a make_heap, push_heap és pop_heap (általában bináris kupacok) halomkezeléséhez, amelyek véletlen hozzáférésű iterátorokon működnek. A metódusok iterátorokat használnak tömbhivatkozásként, és tömb-halom konverziót hajtanak végre.
• A Java 2 Platform Java Pattern Set (az 1.5-ös verziótól) bináris kupac megvalósítást biztosít a java.util.PriorityQueue<E> osztályban.
• A Python rendelkezik egy heapq modullal, amely bináris kupac segítségével valósítja meg a prioritási sorokat. [5]
• A PHP 5.3-as verziója óta a maxheap (SplMaxHeap) és a minheap (SplMinHeap) metódusok elérhetők a szabványos könyvtárban.
• A Perl rendelkezik a bináris, binomiális és fibonacci kupacok megvalósításával az Átfogó Archívum Hálózatban . [6]

Lásd még

• Kazal
• Rendezési algoritmus

Jegyzetek

1. ↑ 1 2 3 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Bevezetés az algoritmusokba. MIT Press / McGraw-Hill.
2. ↑ Iacono, John (2000), Javított felső határ a kupacok párosításához , Proc. 7th Scandinavian Workshop on Algorithm Theory , vol. 1851, Lecture Notes in Computer Science, Springer-Verlag, p. 63–77 , DOI 10.1007/3-540-44985-X_5 
3. ↑ Párhuzamos prioritású sor állandó idejű műveletekkel , < http://www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf > Archiválva : 2011. július 26. a Wayback Machine -nél 
4. ↑ Frederickson, Greg N. (1993), Optimal Algorithm for Selection in a Min-Heap , Information and Computation , vol. 104., Akadémiai Kiadó, p. 197–214, doi : 10.1006/inco.1993.1030 , < http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf > Archivált : 2012. december 3. Machine at the Wayback 
5. ↑ Python heapq . Letöltve: 2011. május 31. Az eredetiből archiválva : 2012. október 18.. (határozatlan)
6. ↑ Perl Heap