ในทางวิทยาการคอมพิวเตอร์ ฮีปซอร์ต หรือ อัลกอริทึมจัดเรียงแบบฮีป (อังกฤษ: heapsort) คือ อัลกอริทึมจัดเรียงที่มีพื้นฐานคือการเปรียบเทียบสมาชิกในอาร์เรย์ (array) โดยใช้โครงสร้างข้อมูลแบบฮีป (heap) เป็นหลักในการจัดเรียง
ในสเตปแรกของการรันฮีปซอร์ต สมาชิกของอาร์เรย์จะถูกจัดเรียงให้เป็นโครงสร้างข้อมูลฮีป เรียกว่า การสร้างฮีป (heapify) เมื่อสร้างเป็นฮีปแล้ว ฮีปซอร์ตจะทำการสลับสมาชิกตัวที่อยู่หน้าสุด (เป็นโหนดด้านบนสุดของฮีป) และตัวล่างสุดของฮีป (ตัวที่อยู่หลังสุดของอาร์เรย์ในส่วนที่ยังไม่ได้จัดเรียง (unsorted part of the array)) ฮีปซอร์ตจะทำแบบนี้ จนกระทั่งอาร์เรย์เรียงจากน้อยไปมากอย่างสมบูรณ์ | |
ประเภท | อัลกอริทึมจัดเรียง |
---|---|
โครงสร้างข้อมูล | แถวลำดับ |
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | (distinct keys) or (equal keys) |
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | total auxiliary |
ฮีปซอร์ตและโครงสร้างข้อมูลฮีป คิดค้นขึ้นโดย ในปี ค.ศ. 1964
ฮีปซอร์ตจัดเป็นหนึ่งในกลุ่มซีเล็กชันซอร์ต (selection sort) กล่าวคือ อัลกอริทึมจะนำตัวที่มีค่าสูงที่สุดในอาร์เรย์ไปไว้ข้างหลังสุด และตัวที่สูงสุดอันดับที่สองตามมา จนถึงตัวสุดท้าย โดยใช้วิธีการสลับ (swaping) แต่ฮีปซอร์ตมีประสิทธิภาพสูงกว่าซีเล็กชันซอร์ตมากกว่าหลายเท่า
เปรียบเทียบ heapsort กับ merge sort และ quicksort
โดยทั่วไปในทางปฏิบัติแล้ว heapsort จะช้ากว่า merge sort และ quicksort และถือเป็นอัลกอริทึมที่ไม่เสถียร (unstable algorithm) กล่าวคือ heapsort จะไม่ทำการรักษาตำแหน่งของเรคคอร์ดในอาร์เรย์ในกรณีที่ตำแหน่งสองตำแหน่งขึ้นไปนั้น มีค่า (value/key) ที่เท่ากัน
อย่างไรก็ดี heapsort ไม่จำเป็นต้องใช้พื้นที่ในการเก็บข้อมูล (memory space) เหมือนกับ merge sort และเวลารันในกรณีที่แย่ที่สุดของ heapsort คือ Θ(nlogn) ทำให้เร็วกว่า quicksort ซึ่งมีเวลารันในกรณีที่แย่ที่สุดคือ O(n2)
ตัวอย่าง
ให้ { 6, 5, 3, 1, 8, 7, 2, 4 } เป็นลิสต์ เราต้องการเรียงสมาชิกของลิสต์นี้จากน้อยที่สุดไปมากที่สุด
การสร้างฮีป
ฮีป | สมาชิกใหม่ใส่เข้าไปในฮีป | สลับ (swap) สมาชิก |
---|---|---|
NULL (ว่างเปล่า) | 6 | |
6 | 5 | |
6, 5 | 3 | |
6, 5, 3 | 1 | |
6, 5, 3, 1 | 8 | |
6, 5, 3, 1, 8 | 5, 8 | |
6, 8, 3, 1, 5 | 6, 8 | |
8, 6, 3, 1, 5 | 7 | |
8, 6, 3, 1, 5, 7 | 3, 7 | |
8, 6, 7, 1, 5, 3 | 2 | |
8, 6, 7, 1, 5, 3, 2 | 4 | |
8, 6, 7, 1, 5, 3, 2, 4 | 1, 4 | |
8, 6, 7, 4, 5, 3, 2, 1 |
การเรียง
ฮีป | สลับ (swap) สมาชิก | ลบ (delete) สมาชิก | อาร์เรย์ที่จัดเรียงแล้ว | ข้อมูล |
---|---|---|---|---|
8, 6, 7, 4, 5, 3, 2, 1 | 8, 1 | สลับ 8 และ 1 เพื่อลบ 8 จากฮีป | ||
1, 6, 7, 4, 5, 3, 2, 8 | 8 | ลบ 8 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | ||
1, 6, 7, 4, 5, 3, 2 | 1, 7 | 8 | สลับ 1 และ 7 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
7, 6, 1, 4, 5, 3, 2 | 1, 3 | 8 | สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
7, 6, 3, 4, 5, 1, 2 | 7, 2 | 8 | สลับ 7 และ 2 เพื่อลบ 7 จากฮีป | |
2, 6, 3, 4, 5, 1, 7 | 7 | 8 | ลบ 7 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
2, 6, 3, 4, 5, 1 | 2, 6 | 7, 8 | สลับ 2 และ 6 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
6, 2, 3, 4, 5, 1 | 2, 5 | 7, 8 | สลับ 2 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
6, 5, 3, 4, 2, 1 | 6, 1 | 7, 8 | สลับ 6 และ 1 เพื่อลบ 6 จากฮีป | |
1, 5, 3, 4, 2, 6 | 6 | 7, 8 | ลบ 6 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
1, 5, 3, 4, 2 | 1, 5 | 6, 7, 8 | สลับ 1 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
5, 1, 3, 4, 2 | 1, 4 | 6, 7, 8 | สลับ 1 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
5, 4, 3, 1, 2 | 5, 2 | 6, 7, 8 | สลับ 5 และ 2 เพื่อลบ 5 จากฮีป | |
2, 4, 3, 1, 5 | 5 | 6, 7, 8 | ลบ 5 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
2, 4, 3, 1 | 2, 4 | 5, 6, 7, 8 | สลับ 2 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
4, 2, 3, 1 | 4, 1 | 5, 6, 7, 8 | สลับ 4 และ 1 เพื่อลบ 4 จากฮีป | |
1, 2, 3, 4 | 4 | 5, 6, 7, 8 | ลบ 4 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
1, 2, 3 | 1, 3 | 4, 5, 6, 7, 8 | สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
3, 2, 1 | 3, 1 | 4, 5, 6, 7, 8 | สลับ 3 และ 1 เพื่อลบ 3 จากฮีป | |
1, 2, 3 | 3 | 4, 5, 6, 7, 8 | ลบ 3 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
1, 2 | 1, 2 | 3, 4, 5, 6, 7, 8 | สลับ 1 และ 2 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป | |
2, 1 | 2, 1 | 3, 4, 5, 6, 7, 8 | สลับ 2 และ 1 เพื่อลบ 2 จากฮีป | |
1, 2 | 2 | 3, 4, 5, 6, 7, 8 | ลบ 2 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
1 | 1 | 2, 3, 4, 5, 6, 7, 8 | ลบ 1 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว | |
1, 2, 3, 4, 5, 6, 7, 8 | เรียงสมบูรณ์ |
อ้างอิง
- "Heapsort". GeeksforGeeks. 2021.
- Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. p. 209. ISBN .
- Williams 1964
- Skiena, Steven (2008). "Searching and Sorting". The Algorithm Design Manual. Springer. p. 109. doi:10.1007/978-1-84800-070-4_4. ISBN .
[H]eapsort is nothing but an implementation of selection sort using the right data structure.
- Panos Louridas (2017). "12: A Menagerie of Sorts". Real-World Algorithms: A Beginner's Guide. MIT Press. p. 326. ISBN .
- László Szabó (2016). "Algoritmusok" (PDF) (ภาษาฮังการี). Budapest: Eötvös Lóránd University.
บรรณานุกรม
- Williams, J. W. J. (1964). "Algorithm 232 – Heapsort". Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284.
แหล่งข้อมูลอื่น
- วิกิมีเดียคอมมอนส์มีสื่อเกี่ยวกับ ฮีปซอร์ต
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
inthangwithyakarkhxmphiwetxr hipsxrt hrux xlkxrithumcderiyngaebbhip xngkvs heapsort khux xlkxrithumcderiyngthimiphunthankhuxkarepriybethiybsmachikinxarery array odyichokhrngsrangkhxmulaebbhip heap epnhlkinkarcderiynghipsxrtinsetpaerkkhxngkarrnhipsxrt smachikkhxngxarerycathukcderiyngihepnokhrngsrangkhxmulhip eriykwa karsranghip heapify emuxsrangepnhipaelw hipsxrtcathakarslbsmachiktwthixyuhnasud epnohnddanbnsudkhxnghip aelatwlangsudkhxnghip twthixyuhlngsudkhxngxareryinswnthiyngimidcderiyng unsorted part of the array hipsxrtcathaaebbni cnkrathngxareryeriyngcaknxyipmakxyangsmburnpraephthxlkxrithumcderiyngokhrngsrangkhxmulaethwladbprasiththiphaphemuxekidkrniaeythisudO nlog n displaystyle O n log n prasiththiphaphemuxekidkrnidithisudO nlog n displaystyle O n log n distinct keys or O n displaystyle O n equal keys prasiththiphaphemuxekidkrnithwipO nlog n displaystyle O n log n primankhwamtxngkarphunthiemuxekidkrniaeythisudO n displaystyle O n total O 1 displaystyle O 1 auxiliaryk hipsxrtaelaokhrngsrangkhxmulhip khidkhnkhunody inpi kh s 1964 hipsxrtcdepnhnunginklumsielkchnsxrt selection sort klawkhux xlkxrithumcanatwthimikhasungthisudinxareryipiwkhanghlngsud aelatwthisungsudxndbthisxngtamma cnthungtwsudthay odyichwithikarslb swaping aethipsxrtmiprasiththiphaphsungkwasielkchnsxrtmakkwahlayethaepriybethiyb heapsort kb merge sort aela quicksorttwxyangxlkxrithumcderiyngthiesthiyr inkarelniph emuxiphthukcderiyngtamxndbdwykarcderiyngthiesthiyr iphelkh 5 thngsxngcatxngxyuinladbediywkninphllphththieriyngladbtamedim aetemuxeriyngdwykareriyngladbthiimesthiyr iphelkh 5 thngsxng xacipxyuintaaehnngtrngkhamkn hlngcakthikareriyngladbsinsudlng odythwipinthangptibtiaelw heapsort cachakwa merge sort aela quicksort aelathuxepnxlkxrithumthiimesthiyr unstable algorithm klawkhux heapsort caimthakarrksataaehnngkhxngerkhkhxrdinxareryinkrnithitaaehnngsxngtaaehnngkhunipnn mikha value key thiethakn xyangirkdi heapsort imcaepntxngichphunthiinkarekbkhxmul memory space ehmuxnkb merge sort aelaewlarninkrnithiaeythisudkhxng heapsort khux 8 nlogn thaiherwkwa quicksort sungmiewlarninkrnithiaeythisudkhux O n2 twxyangih 6 5 3 1 8 7 2 4 epnlist eratxngkareriyngsmachikkhxnglistnicaknxythisudipmakthisud twxyanghipsxrtkarsranghip hip smachikihmisekhaipinhip slb swap smachikNULL wangepla 66 56 5 36 5 3 16 5 3 1 86 5 3 1 8 5 86 8 3 1 5 6 88 6 3 1 5 78 6 3 1 5 7 3 78 6 7 1 5 3 28 6 7 1 5 3 2 48 6 7 1 5 3 2 4 1 48 6 7 4 5 3 2 1kareriyng hip slb swap smachik lb delete smachik xarerythicderiyngaelw khxmul8 6 7 4 5 3 2 1 8 1 slb 8 aela 1 ephuxlb 8 cakhip1 6 7 4 5 3 2 8 8 lb 8 cakhipaelaephimipyngxarerythieriyngaelw1 6 7 4 5 3 2 1 7 8 slb 1 aela 7 enuxngcakphwkmneriyngladbxyangimthuktxnginhip7 6 1 4 5 3 2 1 3 8 slb 1 aela 3 enuxngcakphwkmneriyngladbxyangimthuktxnginhip7 6 3 4 5 1 2 7 2 8 slb 7 aela 2 ephuxlb 7 cakhip2 6 3 4 5 1 7 7 8 lb 7 cakhipaelaephimipyngxarerythieriyngaelw2 6 3 4 5 1 2 6 7 8 slb 2 aela 6 enuxngcakphwkmneriyngladbxyangimthuktxnginhip6 2 3 4 5 1 2 5 7 8 slb 2 aela 5 enuxngcakphwkmneriyngladbxyangimthuktxnginhip6 5 3 4 2 1 6 1 7 8 slb 6 aela 1 ephuxlb 6 cakhip1 5 3 4 2 6 6 7 8 lb 6 cakhipaelaephimipyngxarerythieriyngaelw1 5 3 4 2 1 5 6 7 8 slb 1 aela 5 enuxngcakphwkmneriyngladbxyangimthuktxnginhip5 1 3 4 2 1 4 6 7 8 slb 1 aela 4 enuxngcakphwkmneriyngladbxyangimthuktxnginhip5 4 3 1 2 5 2 6 7 8 slb 5 aela 2 ephuxlb 5 cakhip2 4 3 1 5 5 6 7 8 lb 5 cakhipaelaephimipyngxarerythieriyngaelw2 4 3 1 2 4 5 6 7 8 slb 2 aela 4 enuxngcakphwkmneriyngladbxyangimthuktxnginhip4 2 3 1 4 1 5 6 7 8 slb 4 aela 1 ephuxlb 4 cakhip1 2 3 4 4 5 6 7 8 lb 4 cakhipaelaephimipyngxarerythieriyngaelw1 2 3 1 3 4 5 6 7 8 slb 1 aela 3 enuxngcakphwkmneriyngladbxyangimthuktxnginhip3 2 1 3 1 4 5 6 7 8 slb 3 aela 1 ephuxlb 3 cakhip1 2 3 3 4 5 6 7 8 lb 3 cakhipaelaephimipyngxarerythieriyngaelw1 2 1 2 3 4 5 6 7 8 slb 1 aela 2 enuxngcakphwkmneriyngladbxyangimthuktxnginhip2 1 2 1 3 4 5 6 7 8 slb 2 aela 1 ephuxlb 2 cakhip1 2 2 3 4 5 6 7 8 lb 2 cakhipaelaephimipyngxarerythieriyngaelw1 1 2 3 4 5 6 7 8 lb 1 cakhipaelaephimipyngxarerythieriyngaelw1 2 3 4 5 6 7 8 eriyngsmburnxangxing Heapsort GeeksforGeeks 2021 Brass Peter 2008 Advanced Data Structures Cambridge University Press p 209 ISBN 978 0 521 88037 4 Williams 1964 Skiena Steven 2008 Searching and Sorting The Algorithm Design Manual Springer p 109 doi 10 1007 978 1 84800 070 4 4 ISBN 978 1 84800 069 8 H eapsort is nothing but an implementation of selection sort using the right data structure Panos Louridas 2017 12 A Menagerie of Sorts Real World Algorithms A Beginner s Guide MIT Press p 326 ISBN 978 0 262 03570 5 Laszlo Szabo 2016 Algoritmusok PDF phasahngkari Budapest Eotvos Lorand University brrnanukrm Williams J W J 1964 Algorithm 232 Heapsort Communications of the ACM 7 6 347 348 doi 10 1145 512274 512284 aehlngkhxmulxunwikitaraphasaxngkvs mikhumux tara hruxwithikarekiywkb hipsxrt wikimiediykhxmmxnsmisuxekiywkb hipsxrtbthkhwamkarekhiynopraekrm hrux phasaopraekrmniyngepnokhrng khunsamarthchwywikiphiediyidodykarephimetimkhxmuldk