ฮีปและคิวลำดับความสำคัญ

คิวลำดับความสำคัญ (priority queue) เป็นชนิดข้อมูลนามธรรมที่ให้ผลลัพธ์เป็นสมาชิกที่มีลำดับความสำคัญสูงสุด (หรือต่ำสุด) เสมอ; ฮีป (heap) เป็นโครงสร้างแบบต้นไม้มาตรฐานที่นำมาใช้เพื่อการแทรกและการดึงค่าต่ำสุดอย่างมีประสิทธิภาพ

Definition

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

Scope

หัวข้อนี้ครอบคลุม ADT ของคิวลำดับความสำคัญและการนำไปใช้ในฮีป: ฮีปแบบไบนารีและการแทนด้วยอาร์เรย์, คุณสมบัติของฮีปและการดำเนินการ sift-up/sift-down, heapsort, และฮีปที่สามารถรวมกันได้ขั้นสูง เช่น ฮีปแบบทวินาม (binomial heap) และฮีปแบบฟีโบนัชชี (Fibonacci heap) ที่ช่วยปรับปรุงต้นทุนของการลดคีย์และการรวมกัน หัวข้อนี้เชื่อมโยงกับอัลกอริทึมกราฟ (Dijkstra, Prim) และการจำลองเหตุการณ์ (event-driven simulation) ซึ่งอาศัยคิวลำดับความสำคัญ

Core questions

• การดำเนินการใดบ้างที่กำหนด ADT ของคิวลำดับความสำคัญ และฮีปนำไปใช้อย่างไร?
• คุณสมบัติของฮีปช่วยให้การค้นหาค่าต่ำสุดใช้เวลาคงที่ และการแทรก/ดึงใช้เวลาแบบลอการิทึมได้อย่างไร?
• ฮีปแบบไบนารีถูกจัดเก็บอย่างกะทัดรัดในอาร์เรย์ได้อย่างไร และสร้างขึ้นในเวลาเชิงเส้นได้อย่างไร?
• Heapsort ใช้วิธีการฮีปเพื่อเรียงลำดับแบบ in-place ในเวลา O(n log n) ได้อย่างไร?
• เมื่อใดที่ฮีปที่สามารถรวมกันได้ เช่น ฮีปแบบฟีโบนัชชี ช่วยปรับปรุงอัลกอริทึมที่ลดคีย์บ่อยครั้ง?

Key concepts

• ADT คิวลำดับความสำคัญ
• คุณสมบัติของฮีป
• ฮีปแบบไบนารี
• การแทนฮีปด้วยอาร์เรย์
• sift-up และ sift-down
• การสร้างฮีปในเวลาเชิงเส้น
• heapsort
• ฮีปแบบฟีโบนัชชีและทวินาม

Key theories

คุณสมบัติของฮีปและการแทนด้วยอาร์เรย์

ฮีปแบบไบนารีเป็นต้นไม้ไบนารีที่เกือบสมบูรณ์ (nearly complete binary tree) ซึ่งคีย์ของแต่ละโหนดจะเหนือกว่าคีย์ของโหนดลูก; สามารถจัดเก็บในอาร์เรย์ด้วยการทำดัชนีแม่-ลูกแบบนัย (implicit parent-child indexing) ทำให้การแทรกและการดึงใช้เวลา O(log n) และการค้นหาค่าต่ำสุดใช้เวลา O(1)

ประสิทธิภาพแบบ Amortized ของฮีปแบบฟีโบนัชชี

ฮีปแบบฟีโบนัชชีรองรับการลดคีย์ในเวลา O(1) แบบ amortized และการดึงค่าต่ำสุดในเวลา O(log n) แบบ amortized ซึ่งช่วยปรับปรุงเวลาการทำงานเชิงเส้นกำกับของอัลกอริทึม เช่น Dijkstra และ Prim ที่มีการลดคีย์บ่อยครั้ง

Clinical relevance

คิวลำดับความสำคัญเป็นโครงสร้างพื้นฐานที่จำเป็น: ใช้ในการจัดลำดับงานที่พร้อมในตัวจัดตารางเวลาของระบบปฏิบัติการ, จัดการเหตุการณ์ในการจำลองเหตุการณ์แบบไม่ต่อเนื่อง, ขับเคลื่อนการค้นหาแบบ best-first และ A*, และเป็นส่วนหน้าในอัลกอริทึมของ Dijkstra และ Prim Heapsort นำเสนอการเรียงลำดับแบบ in-place ที่มีประสิทธิภาพ O(n log n) พร้อมการรับประกันขอบเขตกรณีที่เลวร้ายที่สุด

History

J. W. J. Williams ได้นำเสนอฮีปแบบไบนารีและ heapsort ในปี 1964 และ Robert Floyd ได้นำเสนอขั้นตอนการสร้างฮีปแบบเชิงเส้น (linear-time build-heap) ในเวลาไม่นานหลังจากนั้น ฮีปแบบทวินาม (Vuillemin, 1978) และฮีปแบบฟีโบนัชชี (Fredman and Tarjan, 1987) ได้เพิ่มประสิทธิภาพในการรวมและการลดคีย์แบบ amortized ซึ่งช่วยปรับปรุงเวลาการทำงานของอัลกอริทึมกราฟคลาสสิก

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

ทำไมจึงจัดเก็บฮีปแบบไบนารีในอาร์เรย์แทนที่จะใช้พอยน์เตอร์?

ฮีปแบบไบนารีเป็นต้นไม้ไบนารีที่เกือบสมบูรณ์ ดังนั้นโหนดของมันจึงสามารถจับคู่กับดัชนีอาร์เรย์ที่ต่อเนื่องกันได้อย่างชัดเจน: โหนดที่ดัชนี i จะมีโหนดลูกที่ 2i และ 2i+1 ซึ่งช่วยหลีกเลี่ยงค่าใช้จ่ายของพอยน์เตอร์ ปรับปรุงพฤติกรรมของแคช และทำให้การนำทางเป็นเพียงการคำนวณทางคณิตศาสตร์ง่ายๆ

เมื่อใดที่ฮีปแบบฟีโบนัชชีคุ้มค่ากับความซับซ้อนของมัน?

ฮีปแบบฟีโบนัชชีให้การลดคีย์แบบ amortized ในเวลา O(1) ซึ่งช่วยปรับปรุงเวลาการทำงานเชิงเส้นกำกับของอัลกอริทึม เช่น เส้นทางที่สั้นที่สุดของ Dijkstra บนกราฟหนาแน่น ในทางปฏิบัติ ค่าคงที่ขนาดใหญ่ของมันหมายความว่าฮีปแบบไบนารีที่เรียบง่ายกว่ามักจะเร็วกว่า ดังนั้นจึงมีความสำคัญส่วนใหญ่สำหรับขอบเขตทางทฤษฎีและกรณีเฉพาะทาง