ฮีปซอร์ต
ในทางวิทยาการคอมพิวเตอร์ ฮีปซอร์ต หรือ อัลกอริทึมจัดเรียงแบบฮีป (อังกฤษ: heapsort) คือ อัลกอริทึมจัดเรียงที่มีพื้นฐานคือการเปรียบเทียบสมาชิกในอาร์เรย์ (array) โดยใช้โครงสร้างข้อมูลแบบฮีป (heap) เป็นหลักในการจัดเรียง[1]
 ในสเตปแรกของการรันฮีปซอร์ต สมาชิกของอาร์เรย์จะถูกจัดเรียงให้เป็นโครงสร้างข้อมูลฮีป เรียกว่า การสร้างฮีป (heapify) เมื่อสร้างเป็นฮีปแล้ว ฮีปซอร์ตจะทำการสลับสมาชิกตัวที่อยู่หน้าสุด (เป็นโหนดด้านบนสุดของฮีป) และตัวล่างสุดของฮีป (ตัวที่อยู่หลังสุดของอาร์เรย์ในส่วนที่ยังไม่ได้จัดเรียง (unsorted part of the array)) ฮีปซอร์ตจะทำแบบนี้ จนกระทั่งอาร์เรย์เรียงจากน้อยไปมากอย่างสมบูรณ์ | |
| ประเภท | อัลกอริทึมจัดเรียง |
|---|---|
| โครงสร้างข้อมูล | แถวลำดับ |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
| ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | (distinct keys) or (equal keys) |
| ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
| ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | total auxiliary |
ฮีปซอร์ตและโครงสร้างข้อมูลฮีป[2] คิดค้นขึ้นโดย จอห์น (วิลเลียม โจเซฟ) วิลเลียมส์ ในปี ค.ศ. 1964[3]
ฮีปซอร์ตจัดเป็นหนึ่งในกลุ่มซีเล็กชันซอร์ต (selection sort) กล่าวคือ อัลกอริทึมจะนำตัวที่มีค่าสูงที่สุดในอาร์เรย์ไปไว้ข้างหลังสุด และตัวที่สูงสุดอันดับที่สองตามมา จนถึงตัวสุดท้าย โดยใช้วิธีการสลับ (swaping) แต่ฮีปซอร์ตมีประสิทธิภาพสูงกว่าซีเล็กชันซอร์ตมากกว่าหลายเท่า[4]
เปรียบเทียบ heapsort กับ merge sort และ quicksort
แก้
โดยทั่วไปในทางปฏิบัติแล้ว heapsort จะช้ากว่า merge sort และ quicksort และถือเป็นอัลกอริทึมที่ไม่เสถียร (unstable algorithm) กล่าวคือ heapsort จะไม่ทำการรักษาตำแหน่งของเรคคอร์ดในอาร์เรย์ในกรณีที่ตำแหน่งสองตำแหน่งขึ้นไปนั้น มีค่า (value/key) ที่เท่ากัน[5]
อย่างไรก็ดี heapsort ไม่จำเป็นต้องใช้พื้นที่ในการเก็บข้อมูล (memory space) เหมือนกับ merge sort และเวลารันในกรณีที่แย่ที่สุดของ heapsort คือ Θ(nlogn) ทำให้เร็วกว่า quicksort ซึ่งมีเวลารันในกรณีที่แย่ที่สุดคือ O(n2)
ตัวอย่าง
แก้ให้ { 6, 5, 3, 1, 8, 7, 2, 4 } เป็นลิสต์ เราต้องการเรียงสมาชิกของลิสต์นี้จากน้อยที่สุดไปมากที่สุด[6]
การสร้างฮีป
แก้| ฮีป | สมาชิกใหม่ใส่เข้าไปในฮีป | สลับ (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 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.
- ↑ 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.
แหล่งข้อมูลอื่น
แก้
วิกิมีเดียคอมมอนส์มีสื่อเกี่ยวกับ ฮีปซอร์ต
 | บทความการเขียนโปรแกรม หรือ ภาษาโปรแกรมนี้ยังเป็นโครง คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล |