ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัส/priority queue

priority_queue เป็นโครงสร้างข้อมูลที่มาการเรียงลำดับข้อมูลตลอดเวลา

การใช้งานและการประกาศตัวแปร

ต้องนำเข้า header file "queue" โดย #include <queue>

การประกาศตัวแปรของ priority_queue มีได้หลากหลายรูปแบบ คือ

1. ให้ T คือ datatype ใดๆ และ var คือชื่อตัวแปร มีรูปแบบการประกาศตัวแปร priority_queue โดย priority_queue <T> var;
2. หากต้องการเขียน compare class เองก็จะใช้รูปแบบ priority_queue <T,vector<T>,cmpclass> var; รายละเอียด compare class อ่านที่นี่

method

push

คำอธิบาย	เป็นการเพิ่มข้อมูลชนิด T ลง priority_queue เหมือนการ insert ใช้เวลา $O(log(n))$
พารามิเตอร์	มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง priority_queue
คืนค่า	ไม่มี
ฟังก์ชั่นต้นแบบ	void push(T);
ข้อควรระวัง	ไม่มี

pop

คำอธิบาย	เป็นการลบข้อมูลชนิด T ทาง**ด้านปลาย**ของ priority_queue เหมือนการ extract ใช้เวลา $O(log(n))$
พารามิเตอร์	ไม่มี
คืนค่า	ไม่มี
ฟังก์ชั่นต้นแบบ	void pop();
ข้อควรระวัง	หาก size ของ priority_queue เป็น 0 จะเกิด error

top

คำอธิบาย	เป็นการหาค่าที่อยู่**ด้านปลาย**ของ priority_queue ใช้เวลา $O(1)$
พารามิเตอร์	ไม่มี
คืนค่า	ข้อมูลชนิด T ที่อยู่ด้านปลายของ priority_queue
ฟังก์ชั่นต้นแบบ	T top();
ข้อควรระวัง	หาก size ของ priority_queue เป็น 0 จะเกิด error

size

คำอธิบาย	เป็นการหาว่าขณะนี้ priority_queue มีขนาดเท่าไหร่ ใช้เวลา $O(1)$
พารามิเตอร์	ไม่มี
คืนค่า	จำนวนเต็ม บอกถึงขนาดของ priority_queue
ฟังก์ชั่นต้นแบบ	int size();
ข้อควรระวัง	ไม่มี

empty

คำอธิบาย	เป็นการหาว่าขณะนี้ priority_queue ว่างหรือไม่ ใช้เวลา $O(1)$
พารามิเตอร์	ไม่มี
คืนค่า	ค่า true เมื่อ priority_queue ว่าง (ขนาดเป็น 0) ค่า false เมื่อ priority_queue ไม่ว่าง (ขนาดมากกว่า 0)
ฟังก์ชั่นต้นแบบ	bool empty();
ข้อควรระวัง	ไม่มี

รายละเอียดเพิ่มเติม

เนื่องจาก priority_queue จะทำการเรียงข้อมูลตลอดเวลา ดังนั้นจึงต้องมีเกณฑ์ในการเรียงหรือการเปรียบเทียบเกิดขึ้น เพราะ priority_queue ไม่อาจรู้ได้ว่าค่าไหนควรมาก่อนค่าไหน หากไม่มีการเปรียบเทียบเกิดขึ้น

สามารถแบ่งการประกาศ priority_queue ได้เป็น 2 รูปแบบ

• ระบุ compare class จะเหมือนตัวอย่างที่ 2 ในหัวข้อการประกาศตัวแปร ในกรณีนี้ priority_queue จะดูว่าเกณฑ์การเปรียบเทียบค่าเป็นอย่างไรตาม compare class
• ไม่ระบุ compare class จะเหมือนตัวอย่างที่ 1 ในหัวข้อการประกาศตัวแปร ในกรณีนี้ priority_queue จะใช้ less เป็น compare class โดยอัตโนมัติ
  • หาก datatype ที่ระบุเป็น ชนิดตัวแปรพื้นฐาน จะเป็นการเรียงแบบน้อยไปมาก
  • หาก datatype ที่ระบุเป็น std::string จะเป็นการเรียงแบบ lexicographic order
  • หาก datatype ที่ระบุเป็น struct ที่มีการ overloading operator < จะเกิดการเรียงตามที่กำหนดใน overloading operator <
  • หาก datatype ที่ระบุเป็น datatype อื่นๆซึ่ง less ไม่รู้จัก จะเกิด compilation error ขึ้น

หากการเรียงของ priority_queue เป็นการเรียงแบบน้อยไปมาก ข้อมูลด้านหน้าของ priority_queue จะมีค่าน้อยสุดไปเรื่อยๆ จนถึงข้อมูลด้านปลายมีค่ามากสุด แต่ในการใช้ top หรือ pop จะเป็นการดำเนินการกับข้อมูล**ด้านปลาย** เมื่อมีการเรียก top หรือ pop จึงเป็นการดำเนินการกับค่ามากที่สุด ฉะนั้นหากต้องการให้ top , pop ดำเนินการกับค่าอื่นๆแทน ก็ต้องเปลี่ยนวิธีการเปรียบเทียบใหม่ (เช่นต้องการให้ top , pop ดำเนินการกับค่าน้อยสุด ก็ต้องเรียงจากมากไปน้อยแทน)

การใช้ compare class

compare class คือ class/struct ที่สร้างขึ้นมาเพื่อบอกให้ priority_queue รู้ว่า ข้อมูลไหนควรมาก่อน ข้อมูลไหนควรมาหลัง (จะเรียงข้อมูลอย่างไรดี) โดยทั่วไปหากไม่กำหนด compare class ให้ priority_queue จะใช้ less เป็น compare class อัตโนมัติ (นั่นคือเรียงแบบน้อยไปมาก)

หลักการเขียน compare class

• หากต้องการให้ a มาก่อน b ให้ return true
• หากต้องการให้ b มาก่อน a ให้ return false

กรณี a สำคัญเท่า b จะ return true หรือ false ก็ได้ เพราะถ้า a กับ b สำคัญพอๆกัน อะไรจะมาก่อนมันก็ไม่สำคัญ !

ตัวอย่าง compare class โดยเรียง int

struct cmpclass{
    bool operator()(int a, int b){
    	return a < b;
    }
};

จากตัวอย่าง เราสร้าง struct/class ชื่อ cmpclass ภายในมีการ overloading operator () โดยรับค่า a และ b มา กรณี a < b เราจะ return ค่า true ซึ่งก็คือการเรียงลำดับจากน้อยไปมากนั่นเอง และในกรณีนี้ หากมีการเรียกใช้ pop , top ก็จะเป็นการดำเนินการกับค่าใน priority_queue ซึ่งมากที่สุด (เหมือนใช้ less)

หากต้องการให้ pop , top ดำเนินการกับค่าน้อยสุดก็คือต้องเปลี่ยนการเรียงเป็นมากไปน้อยแทน สามารถเขียนโค้ดได้ตามนี้

struct cmpclass{
    bool operator()(int a, int b){
    	return a > b;
    }
};

==== ตัวอย่าง cmpclass โดยเรียง struct ตามค่า p จากน้อยไปมาก

struct T{
    int p,q;
};

struct cmpclass{
    bool operator()(T a, T b){
    	return a.p < b.p;
    }
};

เงี่ยนเลยเเหละ

การ Overloading Operator < ของ struct

วิธีนี้ใช้ได้กับ datatype ที่เป็น struct เท่านั้น

แนวคิดวิธีนี้คือ เราสามารถกำหนดความหมายของ $<$ ขึ้นมาเองให้กับ struct ใดๆได้ เช่น ให้ struct มีจำนวนเต็ม aa กับ bb เป็นสมาชิก เราสามารถกำหนดความหมายของ $<$ ขึ้นมาเองให้ $a<b$ return ค่า true เมื่อ a.aa $>$ b.aa เพราะฉะนั้นหาก a.aa = 3 และ b.aa = 5 จะได้ว่า $b<a$ return ค่า true (เพราะ b.aa $>$ a.aa) แต่ $a<b$ return ค่า false (เพราะ b.aa $\not >$ a.aa)

การเขียนโค้ด เราจะ overloading operator < โดยรับ T เข้ามา จากนั้น เราจะเขียนเปรียบเทียบค่าของ T ที่เพิ่งรับเข้ามากับสมาชิกปัจจุบัน

struct T{
    int aa,bb;
    bool operator<(T p)const{
    	return aa > p.aa;
    }
};

จากโค้ดตัวอย่างเป็นการบอกว่า หาก aa ของตัวปัจจุบัน มีค่ามากกว่า aa ของ struct อีกตัวที่รับเข้ามา จะ return true

เพราะฉะนั้น เมื่อเรากำหนด $<$ ให้ struct เรียบร้อยแล้ว เราก็ไม่จำเป็นจะต้องใช้ cmpclass อีก !

การ pass by reference

ดูเนื้อหาหลักที่ ภาษาซีพลัสพลัส/pass by reference

มีปัญหาอีกอย่างหนึ่งคือ ในกรณีที่ struct มีขนาดใหญ่มาก การส่งผ่าน struct แบบ pass by value บ่อยๆจะเสียเวลามาก ดังนั้น สามารถแก้ไขปัญหาโดย pass by reference แทน หากนำโค้ดจากตัวอย่างที่แล้วมาแก้เพิ่มจะได้ดังนี้

struct T{
    int p,q;
};

struct cmpclass{
    bool operator()(const T& a, const T& b){
    	return a.p < b.p;
    }
};

กล่าวคือ เราจะเปลี่ยน T val ไปเป็น const T& val แทน

ตัวอย่างโค้ด

#include <cstdio>
#include <queue>

using namespace std;

struct ST{
    int a,b;
    bool operator<(const ST &aa)const{
    	return a < aa.a;
    }
};

int main(){
    priority_queue <int> Q;       // []
    Q.push(13);                   // [13]
    Q.push(12);                   // [12,13]
    Q.push(11);                   // [11,12,13]
    Q.push(10);                   // [10,11,12,13]
    printf("%d\n", Q.top());      // => 13
    Q.pop();                      // [10,11,12]
    printf("%d\n", Q.size());     // => 3
    while(not Q.empty()) Q.pop(); // []
    Q.pop()                       // => Error
    Q.top()                       // => Error
    
    ST tmp;
    priority_queue <ST> T;        // []
    tmp.a = 5;
    tmp.b = 3;
    T.push(tmp);                  // [(5,3)]
    tmp.a = 4;
    tmp.b = 10;
    T.push(tmp);                  // [(4,10),(5,3)]
    printf("%d\n", T.top().b);    // => 3
    return 0;
}

สารบัญ

stack

queue

priority_queue

deque

vector

map

set