HEAP SORT

HEAP SORT
การเรียงข้อมูลโดยอาศัยโครงสร้าง heap เป็นการเรียงข้อมูลแบบที่ดีที่สุด เพราะเป็น อัลกอริทึมที่ประกันได้ว่าเวลาที่ใช้ไม่ว่าในกรณีใดจะเป็น O(log 2 n) เสมอ

โครงสร้าง Heap heap เป็นต้นไม้ไบนารีที่มีคุณสมบัติว่าโหนดใด ๆ ในต้นไม้นั้นจะมีค่าคีย์ใหญ่กว่าค่าคีย์ที่อยู่ใน left son และ right son ของมัน (ถ้าโหนดนั้นมีลูก) ตัวอย่างดังรูป(ก) เป็น heap ส่วนรูป(ข) ไม่ใช่ heap

[Only admins are allowed to see this image]

รูป การเปรียบเทียบระหว่างโครงสร้าง heap กับโครงสร้างอื่น




จากนิยามของโครงสร้าง heap เราทราบว่ารูตโหนดของ heap จะเป็นโหนดที่มีค่าคีย์ใหญ่กว่า ดังนั้นจากอันพุตที่กำหนดให้เราต้องสร้าง heap ขึ้นก่อน แล้วทำการเอาต์พุตรูตโหนดก็จะได้ค่าแรก (ค่าใหญ่ที่สุด) ของชุดที่เรียงแล้ว ในกรณีนี้จะเรียงจากมากไปน้อย(อัลกอริทึมที่เราอธิบายถึงจะได้ค่าที่เรียงแล้วจากน้อยไปมาก) หลังจากที่เอาต์พุตค่ารูตโหนดไปแล้ว ต้นไม่ที่เหลืออยู่จะไม่เป็น heap เราต้องมีวิธีการตกแต่งหรือปรับแต่งให้ต้นไม้ที่เหลืออยู่นั้นเป็น heap จะได้เอาต์พุตค่าถัดไปได้ ดังนั้นกระบวนการใหญ่ของการทำ heap sort ประกอบด้วย 3 ขั้นตอนดังนี้

ขั้นที่ 1 สร้างโครงสร้าง heap
ขั้นที่ 2 เอาต์พุตคีย์ที่รูตโหนด
ขั้นที่ 3 ปรับแต่งต้นไม่ที่เหลือให้เป็น heap

การสร้างโครงสร้าง Heap จากชุดอินพุต อาร์เรย์ใด ๆ สามารถถูกตีความเป็นต้นไม้ไบนารีได้ เช่น อาร์เรย์ที่มีค่าดังนี้ (ดูรูป¶Ñ´ä»)

[Only admins are allowed to see this image]


ความสัมพันธ์ระหว่างโครงสร้างอาร์เรย์และโครงสร้าง heap จะมีรูปเป็นต้นไม้ไบนารีดังรูปµèÍ仹Õé

[Only admins are allowed to see this image]

รูปต้นไม้ไบนารีของอาร์เรย์

การสร้าง heap จะสร้างจากค่าอาร์เรย์ที่อ่านเข้ามาทีละค่าโดยจะสร้าง heap ขนาดที่มี I -1 โหนด เมื่อรับอีกโหนดเข้ามาก็จะได้ heap ที่มีขนาด I ทำเรื่อย ๆ จนได้ heap ขนาด n

การอินพุตค่าใหม่เข้าไปใน heap ให้ถูกตำแหน่งค่าตามในต้นไม้ไบนารี หลักการมีดังนี้ (ให้ I เป็นพอยน์เตอร์ชี้ไปยังโหนด Knew)

ขั้นที่ 1 ให้เปรียบเทียบโหนดที่เข้าใหม่กับโหนดที่เป็นพ่อ
IF Knew > K FATHER THEN แลกที่กัน เลื่อน I ไปชี้ยังตำแหน่ง FATHER (นั่นคือ I ติดตาม Knew ขึ้นไป)

ขั้นที่ 2 ทำขั้นที่ 1 เรื่อย ๆ จนทำไม่ได้

[Only admins are allowed to see this image]

ต้นไม้ที่เห็นระหว่างการสร้าง heap นั้น เป็นการตีความข้อมูลในอาร์เรย์ ส่วนความสัมพันธ์ระหว่างพ่อ - ลูก เป็นแบบที่กล่าวมาแล้วข้างต้น หลังจากที่ข้อมูลเรียงในรูปโครงสร้าง heap แล้ว เราจะเอาเอาต์พุตค่ารูตโหนดซึ่งอยุ่ที่ตำแหน่งที่ 1 ในอาร์เรย์ การเอาต์พุตเราจะให้ค่าA(1) แลกที่กับค่าสุดท้ายของอาร์เรย์ A(8) การแทนในรูปต้นไม้ ค่าที่เอาต์พุตไปแล้วจะแทนโดยโหนดสี่เหลี่ยม ต้นไม้ที่ได้ (ไม่นับโหนดสี่เหลี่ยม) ไม่เป็นโครงสร้าง heap จากนี้ต่อไปเราต้องใช้อัลกอริทึมปรับค่าคีย์ต่าง ๆ ในต้นไม้ให้คุณสมบัติ heap



การปรับต้นไม้ที่ได้จากการแลกค่าให้มีคุณสมบัติ Heap การปรับแต่งทำได้โดยเลื่อนค่าที่รูตโหนดจากบนลงมาล่าง ดังนี้

ขั้นที่ 1 ให้ตั้งค่าพอยน์เตอร์ I ชี้ไปยังรูตโหนด

ขั้นที่ 2 ให้เลือกค่าที่ใหญ่ที่สุดระหว่าง left son และ right son ของโหนด I เป็นค่าที่เลื่อนมาอยู่ที่ตำแหน่ง I ส่วนค่าคีย์ที่ตำแหน่ง I ก็เลื่อนไปอยู่ที่ตำแหน่ง left son และ right son ของมันที่มีค่าใหญ่กว่า จากนั้นเลื่อนพอยน์เตอร์ I มาอยู่ที่ตำแหน่งใหม่นี้

ขั้นที่ 3 ทำขั้นที่ 2 จนกว่าจะทำไม่ได้

[Only admins are allowed to see this image]

รูปการปรับต้นไม้ให้มีคุณสมบัติ heap

แสดงถึงการเลื่อนค่า 22 ลงไปยังตำแหน่งถูกต้องของมัน เพื่อที่ทำต้นไม้ที่ได้เป็น heap เมื่อต้นไม้เป็นไปตามรูป (ค) ต้นไม้นั้นจะเป็น heap ซึ่งมีค่าสูงสุด 42 อยู่ที่รูตโหนด เราจะเอาต์พุต 42 ไปอยู่ที่ตำแหน่งสุดท้ายของอาร์เรย์ (ตำแหน่งก่อนค่า 90 ไป 1 ตำแหน่ง) ดังรูป(ก) ส่วนค่าที่อยู่ที่ตำแหน่งนั้น (ค่า 27) ก็ไปอยู่ที่ตำแหน่ง A(1) หรือรูตโหนด จากนั้นก็เริ่มต้นปรับแต่งต้นไม้ใหม่ให้เป็น heap ซึ่งเริ่มโดยตั้งค่า I ชี้ไปยังรูตโหน


*เครดิต [Only admins are allowed to see this link]


ขั้นตอนวิธี Heap sort
Heap sort ใช้ขั้นตอนวิธีสามส่วนในการเรียงลำดับข้อมูล ส่วนแรกเป็นส่วนของการสร้าง Heap ซึ่งเป็น complete binary tree ที่มีคุณสมบติว่าค่าของ parent มีค่ามากกว่าหรือเท่ากับ ค่าของ children โดยที่ children ซ้ายและขวาเป็น Heap มาก่อน ส่วนที่สองเป็นการสร้าง Heap จากข้อมูลทั้งหมด และส่วนสุดท้ายเป็นการจัดเรียงข้อมูลโดยใช้โครงสร้างของ Heap
ข้อมูลเข้า A[1..n], i
ข้อมูลออก การจัดเรียงของข้อมูลใน A ที่ node i มีคุณสมบัติ heap
HEAPIFY(A, i)
1. L = LEFT(i)
2. R = RIGHT(i)
3. if L <= heap-size[A] and A[L] > A[i]
4. then largest = L
5. else largest = i
6. endif
7. if R <= heap-size[A] and A[R] > A[largest]
8. then largest = R
9. endif
10. if largest != i
11. then exchange A[i] with A[largest]
12. HEAPIFY(A, largest)
13. endif
ข้อมูลเข้า A[1..n]
ข้อมูลออก การจัดเรียงของข้อมูลใน A ที่เป็น HEAP ทั้งหมด
BUILD-HEAP(A)
1. heap-size[A] = length[A]
2. for i = floor(length[A]/2) downto 1
3. HEAPIFY(A, i)
4. endfor
ข้อมูลเข้า A[1..n]
ข้อมูลออก การจัดเรียงของข้อมูลใน A
HEAPSORT(A)
1. BUILD-HEAP(A)
2. for i = length[A] downto 2
3. exchange A[1] with A[i]
4. heap-size[A] = heap-size[A] - 1
5. HEAPIFY(A, 1)
6. endfor

*เครดิต [Only admins are allowed to see this link]