資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的配對優先順序佇列（按第一項排序）
優先順序佇列是一種抽象資料型別，用於儲存一組具有優先順序的元素的集合，它支援根據元素的優先順序插入和刪除元素，也就是說，可以隨時刪除具有最高優先順序的元素。優先順序佇列不會像棧、佇列、列表等那樣按照其位置線性儲存元素。優先順序佇列 ADT（抽象資料型別）根據元素的優先順序儲存元素。
優先順序佇列支援以下函式：
Size() - 用於計算優先順序佇列的大小，因為它返回其中的元素數量。
Empty() - 如果優先順序佇列為空，則返回 true，否則返回 false
Insert(element) - 用於將新元素插入優先順序佇列
Min() - 返回具有最小關聯鍵值的元素，如果優先順序佇列為空，則顯示錯誤訊息。
removeMin() - 刪除 min() 函式引用的元素。
任務是在 C++ 中實現配對優先順序佇列的概念，並按第一項排序。
我們可以用類似於堆的方式解決問題，有兩種方法可以解決問題
- 最大優先順序或最大堆
- 最小優先順序或最小堆
堆是一種樹形結構，其中節點以特定順序排列。堆有兩種型別：最小堆和最大堆。在最小堆中，根節點或父節點小於其子節點，而在最大堆中，根節點或父節點大於其子節點。
示例
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
更新於： 2019年12月23日
3K+ 瀏覽量
廣告