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
แต่จะเปลี่ยนจากการเปรียบเทียบเอาค่ามากขึ้นเป็นเอาค่าน้อยที่สุดขึ้นแทน
Sign GuestBook |