Priority Queue ของ Pair ใน C++ (เรียงตาม First)

Priority Queue เป็น Abstract Data Type สำหรับเก็บชุดของ Prioritized Elements รองรับการ Insert และ Delete ตาม Priority นั่นคือ Element ที่มี Priority สูงสุดสามารถลบได้ทุกเมื่อ Priority Queue ไม่เก็บ Elements แบบ Linear ตามตำแหน่งเหมือน Stack, Queue, List ฯลฯ แต่เก็บตาม Priority

Priority Queue รองรับฟังก์ชัน:

• Size() - คำนวณขนาด (จำนวน Elements)
• Empty() - คืน true ถ้า Empty, false ถ้าไม่
• Insert(element) - ใส่ Element ใหม่
• Min() - คืน Element ที่ Key น้อยที่สุด Error ถ้า Empty
• removeMin() - ลบ Element ที่ Min() ชี้ไป

งานคือ Implement Priority Queue ของ Pairs ใน C++ เรียงตาม First Element

แก้ได้คล้าย Heaps มี 2 วิธี:

• Max Priority (Max Heap)
• Min Priority (Min Heap)

Heap เป็นโครงสร้างต้นไม้ที่โหนดจัดเรียงตามลำดับเฉพาะ มี 2 ประเภท: Min Heap (Root น้อยกว่า Child) และ Max Heap (Root มากกว่า Child)

ตัวอย่าง

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)

อัลกอริทึม (Max Heap)

Start
Step 1: ใน 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

ตัวอย่าง Max Heap

#include <bits/stdc++.h>
using namespace std;

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

Min Heap (Min Priority)

อัลกอริทึม

Start
Step 1: ใน 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

ตัวอย่าง Min Heap

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

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