คิวลำดับความสำคัญของคู่ใน C++ (เรียงลำดับก่อน)

คิวลำดับความสำคัญเป็นประเภทข้อมูลนามธรรมสำหรับการจัดเก็บคอลเลกชันขององค์ประกอบที่มีลำดับความสำคัญที่สนับสนุนการแทรกและการลบองค์ประกอบตามลำดับความสำคัญ นั่นคือองค์ประกอบที่มีลำดับความสำคัญเป็นอันดับแรกสามารถลบออกได้ตลอดเวลา คิวลำดับความสำคัญไม่จัดเก็บองค์ประกอบในลักษณะเชิงเส้นตามตำแหน่งขององค์ประกอบ เช่น ในกอง คิว รายการ ฯลฯ คิวลำดับความสำคัญ ADT (ประเภทข้อมูลนามธรรม) จะจัดเก็บองค์ประกอบตามลำดับความสำคัญ

Priority Queue รองรับฟังก์ชันต่อไปนี้ -

ขนาด() − มันถูกใช้ในการคำนวณขนาดของลำดับความสำคัญในขณะที่ส่งกลับจำนวนขององค์ประกอบในนั้น

ว่างเปล่า() − คืนค่า จริง หากคิวลำดับความสำคัญว่างเปล่าและเป็นเท็จ มิฉะนั้น

แทรก (องค์ประกอบ) - ใช้เพื่อแทรกองค์ประกอบใหม่ลงในคิวลำดับความสำคัญ

นาที() − จะส่งคืนองค์ประกอบที่มีค่าคีย์ที่เกี่ยวข้องน้อยที่สุดและแสดงข้อความแสดงข้อผิดพลาดหาก Priority Queue ว่างเปล่า

removeMin() − จะลบองค์ประกอบที่อ้างอิงโดยฟังก์ชัน min()

ภารกิจคือการใช้แนวคิดของคิวลำดับความสำคัญของคู่ใน C ++ เรียงลำดับโดยคนแรก

เราสามารถแก้ปัญหาในรูปแบบกองที่คล้ายกัน มีสองวิธีในการแก้ปัญหา

• ลำดับความสำคัญสูงสุดหรือฮีปสูงสุด
• ลำดับความสำคัญขั้นต่ำหรือฮีปขั้นต่ำ

ฮีปเป็นโครงสร้างต้นไม้ที่โหนดถูกจัดเรียงตามลำดับเฉพาะ ฮีปมีสองประเภทคือ Min heap และ Max heap ในฮีปขั้นต่ำ โหนดรูทหรือโหนดหลักมีขนาดเล็กกว่าโหนดย่อย ในขณะที่ฮีปสูงสุด โหนดรูทหรือโหนดหลักจะใหญ่กว่าโหนดย่อย

ตัวอย่าง

Input: priorityq.push(make_pair(18, 200))
Input: priorityq.push(make_pair(18, 200))
priorityq.push(make_pair(29, 100))
priorityq.push(make_pair(11, 400))
Output: 29 100

Input: priorityq.push(make_pair(10, 200))
priorityq.push(make_pair(20, 100))
priorityq.push(make_pair(19, 400))
Output: 20 100
Through Max priority (Max heap)

อัลกอริทึม

Start
Step 1-> In main function()
   Define priority_queue<pair<int, int> > priorityq
   Call priorityq.push(make_pair(18, 200))
   Call priorityq.push(make_pair(29, 100))
   Call priorityq.push(make_pair(11, 400))
   Set pair<int, int> top = priorityq.top()
   Print top.first and top.second
Stop

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
// main program
int main() {
   priority_queue<pair<int, int> > priorityq;
   priorityq.push(make_pair(18, 200));
   priorityq.push(make_pair(29, 100));
   priorityq.push(make_pair(11, 400));
   pair<int, int> top = priorityq.top();
   cout << top.first << " " << top.second;
   return 0;
}

ผลลัพธ์

29 100

ผ่านลำดับความสำคัญขั้นต่ำ (ฮีปขั้นต่ำ)

อัลกอริทึม

Start
Step 1-> In main function()
   Define priority_queue<pair<int, int> > priorityq
   Call pq.push(make_pair(10, 200))
   Call pq.push(make_pair(20, 100))
   Call pq.push(make_pair(15, 400))
   Set pair<int, int> top = pq.top()
   Print top.first and top.second
Stop

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
// main program
int main() {
   priority_queue<pi, vector<pi>, greater<pi> > pq;
   pq.push(make_pair(10, 200));
   pq.push(make_pair(20, 100));
   pq.push(make_pair(15, 400));
   pair<int, int> top = pq.top();
   cout << top.first << " " << top.second;
   return 0;
}

ผลลัพธ์

10 200