Heap Sort Flash Animate

Delete Max Heap

การ Delete Max Heap จะเป็นการลบค่าที่มากที่สุดออก ดังนั้น ค่าที่ได้ออกมาจะเป็นการเรียงลำดับจากมากไปน้อย ดังนี้

 

ตัวอย่างโจทย์

 

Delete 9

Delete ค่าที่ได้คือค่าที่อยู่ด้านบนสุด ซึ่งก็คือ 9

ให้นำ 9 ออก แล้วนำโหนดสุดท้ายขึ้นมาไว้แทนที่

(ในที่นี้โหนดสุดท้ายคือ 0)

 

 

เมื่อ 0 ขึ้นมาอยู่ตำแหน่งบนสุดแล้ว

ให้นำ 0 ไปเปรียบเทียบกับโหนดลูก

ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 0

จึงสลับตำแหน่ง 0 กับโหนดลูกนั้น

โหนดลูกในที่นี้คือ 7 และ 8 เอาค่าที่มีจำนวนมากที่สุด คือ 8

 

จากนั้นนำ 0 ไปเปรียบเทียบกับโหนดลูกตัวใหม่ต่อไป

ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 0

จึงสลับตำแหน่ง 0 กับโหนดลูกนั้น

โหนดลูกในที่นี้คือ 2 และ 6 เอาค่าที่มีจำนวนมากที่สุด คือ 6

เมื่อ 0 ไม่มี โหนดลูกให้เปรียบเทียบ

ก็เป็นอันเสร็จการเข้าที่ของ 0 ให้ Delete ตัวต่อไปได้เลย

ซึ่งตำแหน่งที่อยู่บนสุดต่อไปก็คือ 8

 

Delete 8

Delete ค่าที่ได้คือค่าที่อยู่ด้านบนสุด ซึ่งก็คือ 8

ให้นำ 8 ออก แล้วนำโหนดสุดท้ายขึ้นมาไว้แทนที่

(ในที่นี้โหนดสุดท้ายคือ 1)

เมื่อ 1 ขึ้นมาอยู่ตำแหน่งบนสุดแล้ว

ให้นำ 1 ไปเปรียบเทียบกับโหนดลูก

ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 1

จึงสลับตำแหน่ง 1 กับโหนดลูกนั้น

โหนดลูกในที่นี้คือ 7 และ 6 เอาค่าที่มีจำนวนมากที่สุด คือ 7

จากนั้นนำ 1 ไปเปรียบเทียบกับโหนดลูกตัวใหม่ต่อไป

ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 1

จึงสลับตำแหน่ง 1 กับโหนดลูกนั้น

โหนดลูกในที่นี้คือ 4 และ 5 เอาค่าที่มีจำนวนมากที่สุด คือ 5

แล้วจึงสลับตำแหน่ง 1 กับโหนดลูกนั้น

เมื่อ 1 ไม่มี โหนดลูกให้เปรียบเทียบ

ก็เป็นอันเสร็จการเข้าีที่ของ 1 ให้ Delete ตัวต่อไปได้เลย

ซึ่งตำแหน่งที่อยู่บนสุดต่อไปก็คือ 7

 

 

 

Delete 7

Delete ค่าที่ได้คือค่าที่อยู่ด้านบนสุด ซึ่งก็คือ 7 ให้นำ 7 ออก แล้วนำโหนดสุดท้ายขึ้นมาไว้แทนที่ (ในที่นี้โหนดสุดท้ายคือ 3) เมื่อ 3 ขึ้นมาอยู่ตำแหน่งบนสุดแล้ว ให้นำ 3 ไปเปรียบเทียบกับโหนดลูก ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 3 จึงสลับตำแหน่ง 3 กับโหนดลูกนั้น โหนดลูกในที่นี้คือ 5 และ 6 เอาค่าที่มีจำนวนมากที่สุด คือ 6 แล้วจึงสลับตำแหน่ง 3 กับโหนดลูกนั้น

 

จากนั้นนำ 3 ไปเปรียบเทียบกับโหนดลูกตัวใหม่ต่อไป ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 3 จึงสลับตำแหน่ง 4 กับโหนดลูกนั้น ในที่นี้ไม่มีโหนดลูกที่มีค่ามากกว่า 3 แล้ว ก็เป็นอันเสร็จการเข้าที่ของ 3 ให้ Delete ตัวต่อไปได้เลย ซึ่งตำแหน่งที่อยู่บนสุดต่อไปก็คือ 6

Delete 6

Delete ค่าที่ได้คือค่าที่อยู่ด้านบนสุด ซึ่งก็คือ 6

ให้นำ 6 ออก แล้วนำโหนดสุดท้ายขึ้นมาไว้แทนที่

(ในที่นี้โหนดสุดท้ายคือ 0)

เมื่อ 0 ขึ้นมาอยู่ตำแหน่งบนสุดแล้ว

ให้นำ 0 ไปเปรียบเทียบกับโหนดลูก

ถ้าโหนดลูกที่มีค่ามากที่สุด มีค่ามากกว่า 0

จึงสลับตำแหน่ง 0 กับโหนดลูกนั้น

โหนดลูกในที่นี้คือ 5 และ 3 เอาค่าที่มีจำนวนมากที่สุด คือ 5

แล้วจึงสลับตำแหน่ง 0 กับโหนดลูกนั้น

จากนั้นนำ 0 ไปเปรียบเทียบกับโหนดลูกตัวใหม่ต่อไป

โหนดลูกในที่นี้คือ 4 และ 1 เอาค่าที่มีจำนวนมากที่สุด คือ 4

จึงสลับตำแหน่ง 0 กับโหนดลูกนั้น

จากนี้ไม่มีโหนดลูกสำหรับ 0 แล้ว

ก็เป็นอันเสร็จการเข้าที่ของ 0 ให้ Delete ตัวต่อไปได้เลย

ซึ่งตำแหน่งที่อยู่บนสุดต่อไปก็คือ 5

 

 

การdeleteหลังจากนี้จะให้วิธีการเดียวกันกับข้างต้นหมด

จึงขอละการอธิบายไว้ค่ะ

 

Delete 5

 

 

Delete 4

 

Delete 3

 

 

Delete 2

 

Delete 1

Delete 0

 

เมื่อนำอันดับการ Delete มาดูอีกที จะพบว่า ตัวเลขเรียบอันดับ จากมากไปน้อย

9 8 7 6 5 4 3 2 1 0

 

ส่วนการทำ Delete Min Heap จะใช้วิธีเดียวกับ Max Heap

แต่จะเปลี่ยนจากการเปรียบเทียบเอาค่ามากขึ้นเป็นเอาค่าน้อยที่สุดขึ้นแทน

 

Back to Heap Sort >>


Sign GuestBook