แถวคอยลำดับความสำคัญ

ในแถวคอยปกติ ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First Out: FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่น การให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท เช่นนี้เราจะสร้าง **แถวคอยลำดับความสำคัญ** () เป็นคิวที่ถึงแม้เข้าก่อน แต่สิ่งที่มีความสำคัญมากกว่าจะได้ออกก่อน ถ้ามีความสำคัญเท่ากัน ข้อมูลที่เข้ามาก่อนจะได้ออกก่อนเช่นเดียวกับแถวคอยปกติ

แถวคอยลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงแถวคอยได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้แถวคอยลำดับความสำคัญในการจัดการทำงาน การตรวจนับ ฯลฯ

## จุดเด่น
แถวคอยลำดับความสำคัญสามารถดึงตัวที่สำคัญที่สุดลัดแถวออกมาก่อน โดยใช้เวลาคงที่ จึงทำให้จัดการทำงานได้อย่างสอดคล้องกับความเป็นจริงมากยิ่งขึ้น ทำให้สามารถจัดลำดับในการทำงานได้ดี เช่น การจัดการทำงานของเครื่องพิมพ์ที่อนุญาตให้งานเล็ก ๆ ได้พิมพ์ก่อน เพื่อจะได้ไม่เสียเวลา

## บริการที่มักจะมี
* เพิ่มรายการแนบด้วยระดับไว้ในแถวคอย (enqueue)
* ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นออกมา (prioritized dequeue)
* ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)

## ตัวอย่างการเขียนโปรแกรม (ภาษา C++)

```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))

## ดูเพิ่ม
* แถวคอย
* แถวคอยสองหน้า

หมวดหมู่:แบบชนิดข้อมูลนามธรรม