สมัครเรียนโทร. 085-350-7540 , 084-88-00-255 , ntprintf@gmail.com
void enqueue(ชนิดตัวแปร ชื่อตัวแปร)
การเพิ่มข้อมูลลงในฮีปจะแตกต่างจากคิวตรงที่ การเอาข้อมูลใส่ในคิวข้อมูลก็สามารถต่อท้ายข้อมูลล่าสุดในคิวได้เลย แต่สำหรับฮีปแม้จะใส่ข้อมูลลงไปท้ายสุดแต่ต้องตรวจสอบด้วยว่าข้อมูลนั้นมากกว่าโหนดพ่อหรือไม่ ถ้ามากกว่าให้สลับตำแหน่งกับโหนดพ่อ ให้โหนดพ่อมาเป็นลูกแทน
รูป 5-7
จากรูปเพิ่ม 80 เข้าไปที่ท้ายสุดของฮีป (ฮีปไล่ข้อมูลจากซ้ายไปขวา) โหนดพ่อตอนนี้เป็น 9 สลับเพราะมีค่ามากกว่าจากนั้นจะได้พ่อเป็นโหนดรากซึ่งมีค่าเท่ากับ 55 สลับ เมื่อเป็นรากย่อมมากสุดแล้ว จบการเพิ่มข้อมูล
รูป 5-8
บรรทัดที่ 45 : สร้างเมท็อด enqueue สำหรับเพิ่มข้อมูลลงในฮีป
บรรทัดที่ 47 : เพิ่มข้อมูลลงในช่องที่ size หรือช่องสุดท้าย
บรรทัดที่ 48 : เมื่อข้อมูลแล้วก็เพิ่มขนาดของ size ด้วย
บรรทัดที่ 49 : สร้างตัวแปร n แทนตำแหน่งสุดท้ายของอาร์เรย์
บรรทัดที่ 50 : สร้างตัว p เก็บค่าว่าโหนดพ่อของตำแหน่งสุดท้าย(ข้อมูลที่เพิ่งเพิ่มลงไป)คือโหนดตำแหน่งอะไร
บรรทัดที่ 51 : ตอนวนลูปให้ดูว่า n ยังมากกว่า 0(ข้อมูลช่องแรกหรือเปล่า) และดูว่าเมื่อเทียบ p(โหนดพ่อ) กับ x(ข้อมูลที่เพิ่งเพิ่มลงไป) ว่าตัวไหนมีค่ามากกว่ากัน
เมท็อด compare ของ Comparator ถ้าได้ค่าน้อยกว่า 0 แสดงว่า ข้อมูลพ่อ data[p] น้อยกว่า x
บรรทัดที่ 53 : ถ้าวนลูปยังไม่ลดเลยขนาดของรากและพบว่าโหนดพ่อน้อยกว่าโหนดลูกให้สลับกัน
บรรทัดที่ 54 : เอาตำแหน่งของ p เป็นไปตำแหน่งของ n
บรรทัดที่ 55 : หาตำแหน่ง p ใหม่ แล้วเทียบไปเรื่อยๆจบสลับไม่ได้ออกจากลูป
ชื่อตัวแปร dequeue()
เมท็อดสำหรับลบข้อมูลออกจากฮีป การลบข้อมูลออกจาก max heap จะลบข้อมูลที่ช่อง 0 ออกเพราะเป็นข้อมูลที่สำคัญที่สุด แต่เมื่อลบข้อมูลต้องเปลี่ยนโครงสร้างของฮีปโดยให้ข้อมูลช่องสุดท้ายมาแทนช่องแรก จากนั้นหาว่าระหว่างลูกทางซ้ายกับลูกทางขวาข้างไหนมีค่ามากกว่ากัน ให้เลือกข้างที่มากกว่าแล้วสลับตำแหน่งกับราก จากนั้นให้เทียบซ้ายขวาอีกรอบแล้วทำการสลับ
รูป5-9
ต้องการลบ 25 ออกจากฮีป เอาขอมูลช่องสุดท้ายซึ่งก็คือ 1 มาแทน จากการเทียบลูกซ้ายขวาของราก ซึ่งตอนนี้เป็น 1 พบว่า 12 มากกว่า 8 จึงให้ 1 สลับกัน 12 จากนั้น 1 มีลูกสองข้าง แต่ 9 มากกว่า 3 จึงให้ 1 สลับกับ 9 ที่ต้องเทียบตัวมากกว่าขึ้นมาเพราะพอมันขึ้นมาแล้วตัวฝั่งที่น้อยกว่าก็จะยังคงน้อยกว่าอยู่ดี
รูป5-10
บรรทัดที่ 59 : สร้างเมท็อด dequeue()
บรรทัดที่ 61 : สร้างตัวแปร t เก็บข้อมูลช่องแรก
บรรทัดที่ 62 : ลบขนาดของ size ลง
บรรทัดที่ 63 : ให้ n เท่ากับข้อมูลช่องที่ size
บรรทัดที่ 64 : หลังจากนั้นเอาข้อมูลช่องที่ size ไปแทนข้อมูลช่องแรก
บรรทัดที่ 65 : เปลี่ยน n เป็นเลข 0 เพราะกลายเป็นช่องแรกไปแล้ว
บรรทัดที่ 67 : สร้างลูป true ไว้ก่อนค่อยไป break เอา
บรรทัดที่ 68: สร้างตัวแปร l หาลูกทางซ้ายของ n
บรรทัดที่ 69: สร้างตัวแปร r หาลูกทางขวาของ n
รูป 5-11
บรรทัดที่ 76: สร้างตัวแปร k
บรรทัดที่ 77-78: เปรียบเทียบข้อมูลโหนดลูกซ้ายขวา ถ้าซ้ายมากกว่าขวา เอาซ้ายไปเก็บใน k
บรรทัดที่ 79-80 : ถ้าขวามากกว่าขวา เอาขวาไปเก็บใน k
บรรทัดที่ 83-84: เมื่อได้ข้อมูลข้างที่มากกว่ากันระหว่างลูกซ้ายและลูกขวาแล้ว เอาข้างที่มากกว่าไปเทียบกับข้อมูลราก ถ้าข้อมูลลูกฝั่งนั้นมากกว่า ให้สลับตำแหน่งกัน
บรรทัดที่ 85: ให้รากเปลี่ยนเป็นเลขตำแหน่งของตัวทีสลับเมื่อกี้
บรรทัดที่ 86-87: ถ้าสลับหมดแล้วก็ break
บรรทัดที่ 92-93: ถ้าลูกซ้ายมากกว่ารากก็สลับตำแหน่งกัน
ชื่อตัวแปร peek()
Peek เป็นการดูข้อมูลตัวที่สำคัญที่สุด ก็ให้ดูข้อมูลช่องที่ศูนย์เลย
รูป5-12
Tag ที่น่าสนใจ: priority_queue heap enqueue priority_queue_implementation dequeue peek data_structure algorithm comparator binary_tree node_swapping
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM
Copyright (c) 2013 expert-programming-tutor.com. All rights reserved. | 085-350-7540 | 084-88-00-255 | ntprintf@gmail.com