Piramis fajta

A Heap sort ( eng.  Heapsort , “Heap sort” [1] ) egy olyan rendezési algoritmus , amely a legrosszabb, átlagosan és a legjobb esetben (vagyis garantáltan) működik az elemek rendezésekor végzett műveleteknél. [2] A felhasznált háttérmemória mennyisége nem függ a tömb méretétől (vagyis ).

Felfogható a buborékrendezés továbbfejlesztéseként , amelyben egy elem több útvonalon lebeg ( min-heap ) / süllyed ( max-heap ).

Létrehozási előzmények

A Heapsort J. Williams javasolta 1964-ben. [egy]

Algoritmus

A Heapssort bináris rendezési fát használ . A válogatófa olyan fa, amely megfelel a következő feltételeknek:

1. Minden levél mélysége vagy , vagy , ami  a fa maximális mélysége.
2. Az érték egyik csúcson sem kisebb (a másik lehetőség nem több, mint) a leszármazottjainak értéke.

A rendezési fa kényelmes adatszerkezete egy olyan tömb Array, amely Array[0] a gyökérben lévő elem, az elem gyermekei Array[i]pedig Array[2i+1]és Array[2i+2].

A rendezési algoritmus két fő lépésből áll:

1. Építse fel a tömb elemeit rendezési fa formájában! :

at .

Ez a lépés műtétet igényel.

2. Egyenként távolítjuk el az elemeket a gyökérből, és újjáépítjük a fát. Azaz első lépésben kicseréljük Array[0]és Array[n-1], Array[0], Array[1], … , Array[n-2]válogatófává alakítjuk. Ezután átrendezzük Array[0]és Array[n-2], Array[0], Array[1]… , Array[n-3]válogatófává alakítjuk. A folyamat addig folytatódik, amíg már csak egy elem marad a rendezési fában. Ekkor Array[0], Array[1], … , Array[n-1] egy rendezett sorozat.

Ez a lépés műtétet igényel.

Előnyök és hátrányok

Előnyök

• Bizonyítottan a legrosszabb eset kötődik .
• Helyre rendez, azaz csak O (1) további memóriát igényel (ha a fa a fentiek szerint van felszerelve).

Hibák

• Instabil  – A stabilitás érdekében ki kell bontani a kulcsot.
• A szinte rendezett tömbökön ez annyi ideig tart, mint a kaotikus adatokon.
• Egy lépésben a kijelölést véletlenszerűen kell elvégezni a tömb teljes hosszában – ezért az algoritmus nem jól kombinálható a gyorsítótárazással és a memóriacserével .
• A módszer "azonnali" közvetlen hozzáférést igényel; nem működik hivatkozott listákon és más szekvenciális hozzáférésű memóriastruktúrákon.
• Nem párhuzamosít.

Az O ( n ) memóriaigényes egyesítési rendezés gyorsabb ( kisebb konstans mellett), és nem romlik le rossz adatok esetén.

Az algoritmus bonyolultsága miatt az erősítést csak nagy n esetén kapjuk meg . Kis n - en (több ezerig) a Shellsort gyorsabb .

Alkalmazás

A "halom rendezés" algoritmust aktívan használják a Linux kernelben .

Jegyzetek

1. ↑ 1 2 Előadások „A párhuzamos programozás modern technológiái”, 5. előadás: Heap rendezés (elérhetetlen link) . Letöltve: 2009. március 20. Az eredetiből archiválva : 2009. március 15. (határozatlan) 
2. ↑ ScienceDirect - Journal of Algorithms: The Analysis of Heapsort . Letöltve: 2017. szeptember 30. Az eredetiből archiválva : 2012. június 4. (határozatlan)

Irodalom

• Levitin A.V. 6. fejezet Transzformációs módszer: kupacok és halmok rendezése // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 275-284. — 576 p. — ISBN 978-5-8459-0987-9
• Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 6. fejezet Heapsort // Algoritmusok: konstrukció és elemzés = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M .: Williams, 2005. - S. 182-188. — ISBN 5-8459-0857-4 .

Linkek

• Heap rendezés  - részletes leírás illusztrációkkal és példa megvalósítással C ++ nyelven. Adott az algoritmus sebességére vonatkozó becslések származtatása és a futási idő mérése valós számítástechnikai rendszeren.
• Rendezés kupac segítségével (heap rendezés)  - érthető leírás illusztrációkkal és példamegvalósítással Pascalban.
• Dynamic Visualization 7 nyílt forráskódú rendezési algoritmusok archiválva 2017. szeptember 20. a Wayback Machine -nél