ดูต้นฉบับสำหรับ ฮีปซอร์ต

{{Infobox Algorithm
|class=[[ขั้นตอนวิธีการเรียงลำดับ|อัลกอริทึมจัดเรียง]]
|image=[[ไฟล์:Sorting heapsort anim.gif]]
|caption=ในสเตปแรกของการรันฮีปซอร์ต สมาชิกของอาร์เรย์จะถูกจัดเรียงให้เป็นโครงสร้างข้อมูล[[ฮีป|ฮีป]] เรียกว่า การสร้างฮีป (heapify) เมื่อสร้างเป็นฮีปแล้ว ฮีปซอร์ตจะทำการสลับสมาชิกตัวที่อยู่หน้าสุด (เป็นโหนดด้านบนสุดของฮีป) และตัวล่างสุดของฮีป (ตัวที่อยู่หลังสุดของอาร์เรย์ในส่วนที่ยังไม่ได้จัดเรียง (unsorted part of the array)) ฮีปซอร์ตจะทำแบบนี้ จนกระทั่งอาร์เรย์เรียงจากน้อยไปมากอย่างสมบูรณ์
|data=[[แถวลำดับ]]
|time=<math>O(n\log n)</math>
|average-time=<math>O(n\log n)</math>
|best-time=<math>O(n\log n)</math> (distinct keys)<br />or <math>O(n)</math> (equal keys)
|space=<math>O(n)</math> total <math>O(1)</math> auxiliary
|optimal=ไม่มี
|name=ฮีปซอร์ต
}}
ในทาง[[วิทยาการคอมพิวเตอร์]] '''ฮีปซอร์ต''' หรือ '''อัลกอริทึมจัดเรียงแบบฮีป''' ({{langx|en|heapsort}}) คือ อัลกอริทึมจัดเรียงที่มีพื้นฐานคือการเปรียบเทียบสมาชิกในอาร์เรย์ (array) โดยใช้โครงสร้างข้อมูลแบบ[[ฮีป (โครงสร้างข้อมูล)|ฮีป]] (heap) เป็นหลักในการจัดเรียง<ref>{{Cite web |title=Heapsort |date=2021 |work=GeeksforGeeks |url=https://www.geeksforgeeks.org/heap-sort/}}</ref>

ฮีปซอร์ตและโครงสร้างข้อมูลฮีป<ref name="brass">{{Cite book |last=Brass |first=Peter |title=Advanced Data Structures |url=https://archive.org/details/advanceddatastru0000bras |publisher=Cambridge University Press |year=2008 |isbn=978-0-521-88037-4 |page=[https://archive.org/details/advanceddatastru0000bras/page/n228 209]}}</ref> คิดค้นขึ้นโดย [[J. W. J. Williams|จอห์น (วิลเลียม โจเซฟ) วิลเลียมส์]] ในปี ค.ศ. 1964<ref>{{harvnb|Williams|1964}}</ref>

ฮีปซอร์ตจัดเป็นหนึ่งในกลุ่ม[[การเรียงลำดับแบบเลือก|ซีเล็กชันซอร์ต]] (selection sort) กล่าวคือ อัลกอริทึมจะนำตัวที่มีค่าสูงที่สุดในอาร์เรย์ไปไว้ข้างหลังสุด และตัวที่สูงสุดอันดับที่สองตามมา จนถึงตัวสุดท้าย โดยใช้วิธีการสลับ (swaping) แต่ฮีปซอร์ตมีประสิทธิภาพสูงกว่าซีเล็กชันซอร์ตมากกว่าหลายเท่า<ref>{{Cite book |first=Steven |last=Skiena |title=The Algorithm Design Manual |url=https://archive.org/details/algorithmdesignm0000skie |publisher=Springer |year=2008 |page=[https://archive.org/details/algorithmdesignm0000skie/page/n128 109] |chapter=Searching and Sorting |isbn=978-1-84800-069-8 |quote=[H]eapsort is nothing but an implementation of selection sort using the right data structure. |doi=10.1007/978-1-84800-070-4_4}}<!--DOI for chapter--></ref>

== เปรียบเทียบ heapsort กับ merge sort และ quicksort ==
[[ไฟล์:Sorting stability playing cards.svg|thumb|ตัวอย่างอัลกอริทึมจัดเรียงที่เสถียร: ในการเล่นไพ่ เมื่อไพ่ถูกจัดเรียงตามอันดับด้วยการจัดเรียงที่เสถียร ไพ่เลข 5 ทั้งสองจะต้องอยู่ในลำดับเดียวกันในผลลัพธ์ที่เรียงลำดับตามเดิม แต่เมื่อเรียงด้วยการเรียงลำดับที่ไม่เสถียร ไพ่เลข 5 ทั้งสอง อาจไปอยู่ในตำแหน่งตรงข้ามกัน หลังจากที่การเรียงลำดับสิ้นสุดลง]]
โดยทั่วไปในทางปฏิบัติแล้ว heapsort จะช้ากว่า [[การเรียงลำดับแบบผสาน|merge sort]] และ [[ควิกซอร์ต|quicksort]] และถือเป็นอัลกอริทึมที่ไม่เสถียร (unstable algorithm) กล่าวคือ heapsort จะไม่ทำการรักษาตำแหน่งของเรคคอร์ดในอาร์เรย์ในกรณีที่ตำแหน่งสองตำแหน่งขึ้นไปนั้น มีค่า (value/key) ที่เท่ากัน<ref>{{Cite book |title=Real-World Algorithms: A Beginner's Guide |author=Panos Louridas |date=2017 |page=326 |chapter-url=https://books.google.co.th/books?id=_pJPDgAAQBAJ&pg=PA326#v=onepage&q&f=false |chapter=12: A Menagerie of Sorts |publisher=MIT Press |isbn=978-0-262-03570-5}}</ref>

อย่างไรก็ดี heapsort ไม่จำเป็นต้องใช้พื้นที่ในการเก็บข้อมูล (memory space) เหมือนกับ merge sort และเวลารันในกรณีที่แย่ที่สุดของ heapsort คือ Θ(nlogn) ทำให้เร็วกว่า quicksort ซึ่งมีเวลารันในกรณีที่แย่ที่สุดคือ O(n<sup>2</sup>)

== ตัวอย่าง ==
ให้ { 6, 5, 3, 1, 8, 7, 2, 4 } เป็นลิสต์ เราต้องการเรียงสมาชิกของลิสต์นี้จากน้อยที่สุดไปมากที่สุด<ref>{{Cite web |author=László Szabó |title=Algoritmusok |location=Budapest |date=2016 |publisher=Eötvös Lóránd University |url=https://www.inf.elte.hu/dstore/document/329/szabo_laszlo_alg2016.pdf |language=hu}}</ref>
[[ไฟล์:Heapsort-example.gif|right|thumb|350x350px|ตัวอย่างฮีปซอร์ต]]

=== การสร้างฮีป ===
{| class="wikitable"
!ฮีป
!สมาชิกใหม่ใส่เข้าไปในฮีป
!สลับ (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
|
|
|}

=== การเรียง ===
{| class="wikitable"
!ฮีป
!สลับ (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
|
| style="text-align: right;" |8
|สลับ 1 และ 7 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|7, 6, '''1''', 4, 5, '''3''', 2
|1, 3
|
| style="text-align: right;" |8
|สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|'''7''', 6, 3, 4, 5, 1, '''2'''
|7, 2
|
| style="text-align: right;" |8
|สลับ 7 และ 2 เพื่อลบ 7 จากฮีป
|-
|2, 6, 3, 4, 5, 1, '''7'''
|
|7
| style="text-align: right;" |8
|ลบ 7 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|'''2''', '''6''', 3, 4, 5, 1
|2, 6
|
| style="text-align: right;" |7, 8
|สลับ 2 และ 6 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|6, '''2''', 3, 4, '''5''', 1
|2, 5
|
| style="text-align: right;" |7, 8
|สลับ 2 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|'''6''', 5, 3, 4, 2, '''1'''
|6, 1
|
| style="text-align: right;" |7, 8
|สลับ 6 และ 1 เพื่อลบ 6 จากฮีป
|-
|1, 5, 3, 4, 2, '''6'''
|
|6
| style="text-align: right;" |7, 8
|ลบ 6 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|'''1''', '''5''', 3, 4, 2
|1, 5
|
| style="text-align: right;" |6, 7, 8
|สลับ 1 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|5, '''1''', 3, '''4''', 2
|1, 4
|
| style="text-align: right;" |6, 7, 8
|สลับ 1 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|'''5''', 4, 3, 1, '''2'''
|5, 2
|
| style="text-align: right;" |6, 7, 8
|สลับ 5 และ 2 เพื่อลบ 5 จากฮีป
|-
|2, 4, 3, 1, '''5'''
|
|5
| style="text-align: right;" |6, 7, 8
|ลบ 5 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|'''2''', '''4''', 3, 1
|2, 4
|
| style="text-align: right;" |5, 6, 7, 8
|สลับ 2 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|'''4''', 2, 3, '''1'''
|4, 1
|
| style="text-align: right;" |5, 6, 7, 8
|สลับ 4 และ 1 เพื่อลบ 4 จากฮีป
|-
|1, 2, 3, '''4'''
|
|4
| style="text-align: right;" |5, 6, 7, 8
|ลบ 4 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|'''1''', 2, '''3'''
|1, 3
|
| style="text-align: right;" |4, 5, 6, 7, 8
|สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|'''3''', 2, '''1'''
|3, 1
|
| style="text-align: right;" |4, 5, 6, 7, 8
|สลับ 3 และ 1 เพื่อลบ 3 จากฮีป
|-
|1, 2, '''3'''
|
|3
| style="text-align: right;" |4, 5, 6, 7, 8
|ลบ 3 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|'''1''', '''2'''
|1, 2
|
| style="text-align: right;" |3, 4, 5, 6, 7, 8
|สลับ 1 และ 2 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
|-
|'''2''', '''1'''
|2, 1
|
| style="text-align: right;" |3, 4, 5, 6, 7, 8
|สลับ 2 และ 1 เพื่อลบ 2 จากฮีป
|-
|1, '''2'''
|
|2
| style="text-align: right;" |3, 4, 5, 6, 7, 8
|ลบ 2 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|'''1'''
|
|1
| style="text-align: right;" |2, 3, 4, 5, 6, 7, 8
|ลบ 1 จากฮีปและเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
|-
|
|
|
| style="text-align: right;" |1, 2, 3, 4, 5, 6, 7, 8
|เรียงสมบูรณ์
|}

== อ้างอิง ==
{{รายการอ้างอิง}}

=== บรรณานุกรม ===
* {{Cite journal |first=J. W. J. |last=Williams |title=Algorithm 232 – Heapsort |year=1964 |journal=Communications of the ACM |volume=7 |issue=6 |pages=347{{Hyphen}}348 |doi=10.1145/512274.512284}}

== แหล่งข้อมูลอื่น ==
{{วิกิตำราอังกฤษ|Algorithm Implementation/Sorting/Heapsort}}
* {{คอมมอนส์-หมวดหมู่-บรรทัด|Heap sort|ฮีปซอร์ต}}

[[หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ]]
[[หมวดหมู่:ฮีป (โครงสร้างข้อมูล)]]
[[หมวดหมู่:การเรียงแบบเปรียบเทียบ]]
{{โครงการเขียนโปรแกรม}}