คิวลำดับความสำคัญ
จากวิกิพีเดีย สารานุกรมเสรี
| คิวลำดับความสำคัญ | |
|---|---|
| ความสำคัญของลำดับ | FIFO (First In Fast Out) แต่เรียงตามลำดับความสำคัญ |
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
| วิธีการเข้าถึง(access) | ENQUEUE/DEQUEUE (เรียงตามลำดับความสำคัญ) |
| เวลาที่ใช้ในการเข้าถึง | O (1) |
| โครงสร้างข้อมูลที่มีรูปแบบนี้ | ฮีป |
ในคิวปกติ ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่นการให้คิวงานที่เล็๋กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท แบบนี้เราจะสร้าง คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ (Priority Queue) เป็นคิวที่ถึงแม้เข้าก่อน แต่สิ่งที่มีความสำคัญมากกว่าจะได้ออกก่อน ถ้ามีความสำคัญเท่ากัน ข้อมูลที่เข้ามาก่อนจะได้ออกก่อนเช่นเดียวกับคิวปกติ
คิวลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงคิวได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้คิวลำดับความสำคัญในการจัดการทำงาน การตรวจนับ ฯลฯ
เนื้อหา |
[แก้] จุดเด่นของคิวลำดับความสำคัญ
คิวลำดับความสำคัญ สามารถดึงตัวที่สำคัญที่สุดในคิว ลัดคิวออกมาก่อน โดยใช้เวลาคงที่ จึงทำให้จัดการทำงานได้อย่างสอดคล้องกับความเป็นจริงมากยิ่งขึ้น ทำให้สามารถจัดลำดับในการทำงานได้ดี เช่น การจัดการทำงานของเครื่องพิมพ์ที่อนุญาตให้งานเล็กๆได้พิมพ์ก่อน เพื่อจะได้ไม่เสียเวลา
[แก้] บริการที่มักจะมี
- เพิ่มรายการแนบด้วยระดับไว้ในคิว (enqueue)
- ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นกลับมา (prioritized dequeue)
- ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)
[แก้] ความเร็วที่ใช้ในการทำงาน
ถึงแม้ว่าการเอาออกของข้อมูลที่สำคัญที่สุดอาจยุ่งยาก แต่ด้วยการจัดการที่เหมาะสม เราสามารถรักษาความเร็วการทำงานของคิวลำดับความสำคัญไว้ที่ O (1) ได้
[แก้] โครงสร้างข้อมูลที่เป็นคิวลำดับความสำคัญ
- การใช้คิวธรรมดาแต่ค้นหาตัวสำคัญที่สุด วิธีนี้จะทำให้การ dequeue ใช้เวลา O (1)
- การใช้คิวตะกร้า (bucket queue) โดยการสร้างคิวธรรมดาหลายๆคิว แต่ละคิวเก็บลำดับความสำคัญที่เท่าๆกัน และเรียง dequeue ที่ำลำดับสำคัญมากสุดลงมา วิธีนี้จัดการยากพอสมควร
- วิธีที่นิยมที่สุดคือ ฮีป(heap) เป็นการนำแนวคิดต้นไม้ในเชิงการเรียงลำดับให้ตัวที่สำคัญที่สุดอยู่บนๆ และนำตัวบนสุดมาตอบ การจัดการเช่นนี้ทำให้ การทำงานค่อนข้างจะใช้เวลาคงที่ (O (1))
