ฮีปซอร์ต
From Wikipedia, the free encyclopedia
ในทางวิทยาการคอมพิวเตอร์ ฮีปซอร์ต หรือ อัลกอริทึมจัดเรียงแบบฮีป (อังกฤษ: heapsort) คือ อัลกอริทึมจัดเรียงที่มีพื้นฐานคือการเปรียบเทียบสมาชิกในอาร์เรย์ (array) โดยใช้โครงสร้างข้อมูลแบบฮีป (heap) เป็นหลักในการจัดเรียง[1]
ข้อมูลเบื้องต้น ประเภท, โครงสร้างข้อมูล ...
ในสเตปแรกของการรันฮีปซอร์ต สมาชิกของอาร์เรย์จะถูกจัดเรียงให้เป็นโครงสร้างข้อมูลฮีป เรียกว่า การสร้างฮีป (heapify) เมื่อสร้างเป็นฮีปแล้ว ฮีปซอร์ตจะทำการสลับสมาชิกตัวที่อยู่หน้าสุด (เป็นโหนดด้านบนสุดของฮีป) และตัวล่างสุดของฮีป (ตัวที่อยู่หลังสุดของอาร์เรย์ในส่วนที่ยังไม่ได้จัดเรียง (unsorted part of the array)) ฮีปซอร์ตจะทำแบบนี้ จนกระทั่งอาร์เรย์เรียงจากน้อยไปมากอย่างสมบูรณ์ | |
ประเภท | อัลกอริทึมจัดเรียง |
---|---|
โครงสร้างข้อมูล | แถวลำดับ |
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | (distinct keys) or (equal keys) |
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | total auxiliary |
|
ปิด
ฮีปซอร์ตและโครงสร้างข้อมูลฮีป[2] คิดค้นขึ้นโดย จอห์น (วิลเลียม โจเซฟ) วิลเลียมส์ ในปี ค.ศ. 1964[3]
ฮีปซอร์ตจัดเป็นหนึ่งในกลุ่มซีเล็กชันซอร์ต (selection sort) กล่าวคือ อัลกอริทึมจะนำตัวที่มีค่าสูงที่สุดในอาร์เรย์ไปไว้ข้างหลังสุด และตัวที่สูงสุดอันดับที่สองตามมา จนถึงตัวสุดท้าย โดยใช้วิธีการสลับ (swaping) แต่ฮีปซอร์ตมีประสิทธิภาพสูงกว่าซีเล็กชันซอร์ตมากกว่าหลายเท่า[4]