แถวคอยลำดับความสำคัญ
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ในแถวคอยปกติ ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่นการให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท เช่นนี้เราจะสร้าง แถวคอยลำดับความสำคัญ (อังกฤษ: Priority Queue) เป็นคิวที่ถึงแม้เข้าก่อน แต่สิ่งที่มีความสำคัญมากกว่าจะได้ออกก่อน ถ้ามีความสำคัญเท่ากัน ข้อมูลที่เข้ามาก่อนจะได้ออกก่อนเช่นเดียวกับแถวคอยปกติ
แถวคอยลำดับความสำคัญ | |
---|---|
ความสำคัญของลำดับ | FIFO (First In Fast Out) แต่เรียงตามลำดับความสำคัญ |
การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
เวลาที่ใช้ในการเข้าถึง | ENQUEUE/DEQUEUE (เรียงตามลำดับความสำคัญ) |
โครงสร้างที่นำไปใช้ | ฮีป |
แถวคอยลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงแถวคอยได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้แถวคอยลำดับความสำคัญในการจัดการทำงาน การตรวจนับ ฯลฯ
จุดเด่น
แก้แถวคอยลำดับความสำคัญสามารถดึงตัวที่สำคัญที่สุดลัดแถวออกมาก่อน โดยใช้เวลาคงที่ จึงทำให้จัดการทำงานได้อย่างสอดคล้องกับความเป็นจริงมากยิ่งขึ้น ทำให้สามารถจัดลำดับในการทำงานได้ดี เช่น การจัดการทำงานของเครื่องพิมพ์ที่อนุญาตให้งานเล็กๆได้พิมพ์ก่อน เพื่อจะได้ไม่เสียเวลา
บริการที่มักจะมี
แก้- เพิ่มรายการแนบด้วยระดับไว้ในแถวคอย (enqueue)
- ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นออกมา (prioritized dequeue)
- ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)
ตัวอย่างการเขียนโปรแกรม (ภาษา C++)
แก้#include <bits/stdc++.h>
using namespace std;
class node{
public:
int age;
string name;
node(int a, string b){
age = a;
name = b;
}
};
bool operator<(const node& a, const node& b) {
node temp1=a,temp2=b;
if(a.age != b.age)
return a.age > b.age;
else{
return temp1.name.append(temp2.name) > temp2.name.append(temp1.name);
}
}
int main(){
priority_queue<node> pq;
node b(23,"Somchai");
node a(22,"Pongsak");
node c(22,"Manee");
pq.push(b);
pq.push(a);
pq.push(c);
int size = pq.size();
for (int i = 0; i < size; ++i)
{
cout<<pq.top().age<<" "<<pq.top().name<<"\n";
pq.pop();
}
}
จากโปรแกรมข้างต้น เราจะทำการสร้าง แถวคอย โดยโปรแกรมมีเงื่อนไขว่า ใครที่อายุ(Age)น้อยที่สุด จะถูกเรียกชื่อก่อนเสมอ โดยหากมีหลายคนที่อายุเท่ากัน คนที่ถูกเพิ่มเข้าไปในคิวภายหลังจากถูกเรียกก่อนเสมอ
ลำดับการเพิ่มข้อมูล
แก้- Somchai อายุ 23 ปี >> node a(23,"Somchai");
- Pongsak อายุ 22 ปี >> node b(22,"Pongsak");
- Manee อายุ 22 ปี >> node c(22,"Manee");
ผลการทำงานของโปรแกรม
แก้22 Manee
22 Pongsak
23 Somchai
จากผลการทำงานของโปรแกรมข้างต้น จะสังเกตได้ว่า ถึงแม้ Somchai จะมาก่อน แต่ว่าจะถูกเรียกท้ายสุดเพราะอายุมากที่สุด ส่วน Manee จะถูกเรียกเป็นอันดับแรก ถึงแม้ว่าจะอายุเท่ากันกับ Pongsak แต่ว่า Manee มาทีหลังสุด ดังนั้นจึงได้ความสำคัญมากกว่า Pongsak ตามหลักการของ "แถวคอยลำดับความสำคัญ (Priority queue)"
ความเร็วที่ใช้ในการทำงาน
แก้ถึงแม้ว่าการเอาออกของข้อมูลที่สำคัญที่สุดอาจยุ่งยาก แต่ด้วยการจัดการที่เหมาะสม เราสามารถรักษาความเร็วการทำงานของแถวคอยลำดับความสำคัญไว้ที่ O (1) ได้
โครงสร้างข้อมูล
แก้- การใช้แถวคอยธรรมดาแต่ค้นหาตัวสำคัญที่สุด วิธีนี้จะทำให้การคืนค่ารายการใช้เวลา O (1)
- การใช้แถวคอยตะกร้า (bucket queue) โดยการสร้างแถวคอยธรรมดาหลายๆแถว แต่ละแถวเก็บลำดับความสำคัญที่เท่าๆกัน และเรียงลำดับที่สำคัญมากสุดลงมา วิธีนี้จัดการยากพอสมควร
- วิธีที่นิยมที่สุดคือ ฮีป (heap) เป็นการนำแนวคิดต้นไม้ในเชิงการเรียงลำดับให้ตัวที่สำคัญที่สุดอยู่บนๆ และนำตัวบนสุดมาตอบ การจัดการเช่นนี้ทำให้ การทำงานค่อนข้างจะใช้เวลาคงที่ (O (1))