Priority Queue คืออะไร?
Priority queue เป็นชนิดข้อมูลนามธรรมสำหรับเก็บชุดขององค์ประกอบที่มีลำดับความสำคัญ รองรับการแทรกและลบองค์ประกอบตามลำดับความสำคัญ นั่นคือ องค์ประกอบที่มีลำดับความสำคัญสูงสุดสามารถลบได้ทุกเมื่อ Priority queue ไม่ได้เก็บองค์ประกอบในรูปแบบเชิงเส้นตามตำแหน่งเหมือน Stacks, Queues, List ฯลฯ Priority queue ADT เก็บองค์ประกอบตามลำดับความสำคัญของพวกมัน
Priority Queue รองรับฟังก์ชันต่อไปนี้
- Size() - ใช้คำนวณขนาดของ priority queue โดยคืนจำนวนองค์ประกอบในมัน
- Empty() - คืนค่า true ถ้า Priority Queue ว่าง และ false ถ้าไม่ว่าง
- Insert(element) - ใช้แทรกองค์ประกอบใหม่เข้า Priority Queue
- Min() - คืนค่าองค์ประกอบที่มีคีย์น้อยที่สุด และแสดงข้อความผิดพลาดถ้า Priority Queue ว่าง
- removeMin() - ลบองค์ประกอบที่อ้างอิงโดยฟังก์ชัน min()
ตารางด้านล่างแสดงผลของการดำเนินการบน priority queue
อัลกอริทึม
เริ่ม
ขั้นตอน 1 → ประกาศฟังก์ชันแสดงองค์ประกอบใน Priority Queue
void display(priority_queue <int> Pq)
ประกาศและตั้งค่า priority_queue <int> que = Pq
วนลูป While (!que.empty())
เรียก que.top()
เรียก que.pop()
จบวน
ขั้นตอน 2 → ใน main()
สร้างออบเจกต์ priority_queue <int> Pq
เรียก push() เพื่อแทรกองค์ประกอบใน priority queue เป็น Pq.push(1)
เรียก display(Pq)
เรียกเพื่อตรวจสอบขนาด priority queue Pq.size()
เรียกเพื่อแสดงองค์ประกอบบนสุดของ priority queue Pq.top()
เรียกเพื่อลบองค์ประกอบของ priority queue Pq.pop()
เรียก display(Pq)
หยุด
ตัวอย่างโค้ด C++
#include <iostream>
#include <queue>
using namespace std;
void display(priority_queue <int> Pq) {
priority_queue <int> que = Pq;
while (!que.empty()) {
cout << '\t' << que.top();
que.pop();
}
//cout << '\n';
}
int main () {
priority_queue <int> Pq;
Pq.push(1);
Pq.push(3);
Pq.push(5);
Pq.push(7);
Pq.push(9);
cout << "The priority queue is : ";
display(Pq);
cout << "\nPrioriy queue size using size() : " << Pq.size();
cout << "\nFirst element of priority queue using top(): " << Pq.top();
cout << "\nremoving element using pop() : ";
Pq.pop();
display(Pq);
return 0;
}
ผลลัพธ์
The priority queue is : 9 7 5 3 1 Prioriy queue size using size() : 5 First element of priority queue using top(): 9 removing element using pop() : 7 5 3 1
