優先級佇列(Priority Queue)
佇列是一種特征為FIFO的資料結構，每次從佇列中取出的是最早加入佇列中的元素，但是，許多應用需要另一種佇列，每次從佇列中取出的應是具有最高優先權的元素，這種佇列就是優先級佇列(Priority Queue)，也稱為優先權佇列，
1. 優先級佇列的概念
優先級佇列的定義
優先級佇列是不同于先進先出佇列的另一種佇列，每次從佇列中取出的是具有最高優先權的元素，
優先級佇列的特點
- 優先級佇列是0個或多個元素的集合，每個元素都有一個優先權或值，
- 當給每個元素分配一個數字來標記其優先級時，可設較小的數字具有較高的優先級，這樣更方便地在一個集合中訪問優先級最高的元素，并對其進行查找和洗掉操作，
- 對優先級佇列，執行的操作主要有：(1)查找，(2)插入，(3)洗掉，
- 在最小優先級佇列(min Priority Queue)中，查找操作用來搜索優先權最小的元素，洗掉操作用來洗掉該元素，
- 在最大優先級佇列(max Priority Queue)中，查找操作用來搜索優先權最大的元素，洗掉操作用來洗掉該元素，
- 插入操作均只是簡單地把一個新的元素加入到佇列中，
- 注：每個元素的優先級根據問題的要求而定，當從優先級佇列中洗掉一個元素時，可能出現多個元素具有相同的優先權，在這種情況下，把這些具有相同優先權的元素視為一個先來先服務的佇列，按他們的入隊順序進行先后處理，
2.優先級佇列的使用
頭檔案：#include < queue >
優先級佇列默認是最大優先級佇列
介面介紹
| 函式宣告 | 函式說明 |
|---|---|
| priority_queue() / priority_queue(first, last) | 構造一個空的優先級佇列 |
| empty( ) | 判斷優先級佇列是否為空，為慷訓傳true |
| empty( ) | 判斷優先級佇列是否為空，為慷訓傳true |
| top( ) | 獲取優先級佇列中最大或者最小的元素，即堆頂元素 |
| push(x) | 將x元素插入到優先級佇列中 |
| pop() | 洗掉優先級佇列中最大或者最小的元素， 即洗掉堆頂元素 |
測驗代碼：
void test()
{
priority_queue<int> pq;
pq.push(13);
pq.push(14);
pq.push(9);
pq.push(23);
pq.push(12);
pq.push(22);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
測驗結果：默認是最大優先級佇列，所以堆頂元素一直是最大的元素
如何將創建最小優先級佇列----
優先級佇列原型：
泛型介紹：T為優先級佇列存盤的資料型別；Container為優先級佇列中存盤資料的容器；Compare偽函式，決定是最大優先級佇列還是最小優先級佇列
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
創建最小優先級佇列：
priority_queue<int, vector<int>, greater<int>> pq;
測驗結果：
優先級佇列存放自定義型別時，需要自定義型別支持比較的操作，
class A
{
public:
A(int a = 1)
:_a(a)
{}
//支持比較函式
bool operator<(const A& a) const
{
return _a < a._a;
}
bool operator>(const A& a) const
{
return _a > a._a;
}
int _a;
};
測驗結果：
應用場景：Top-K問題
陣列中的第K個最大元素
代碼：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int> pq(nums.begin(), nums.end());
while (--k)
pq.pop();
return pq.top();
}
};
3.優先級佇列的實作
標準容器類vector和deque(雙端佇列)滿足實作優先級佇列的需求，庫中底層默認是使用Vector容器來實作的，我們現在就利用vector簡單模擬實作
private:
vector<T> con;
向下調整演算法
向下調整演算法用于優先級佇列的洗掉介面的實作
void shiftDown()
{
int parent = 0;
int child = 2 * parent + 1;
while (child < con.size())
{
if (child + 1 < con.size() && con[child] < con[child + 1])
{
++child;
}
if (con[parent] < con[child])
{
swap(con[parent], con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
向上調整演算法
向上調整演算法用于優先級佇列的插入介面的實作
//向上調整
void shiftUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (con[parent] < con[child])
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
push()
- 將資料插入到容器的尾端
- 進行向上調整演算法，建成堆
void push(const T& val)
{
//尾插
con.push_back(val);
shiftUp(con.size() - 1);
}
pop()
- 將收尾資料進行交換
- 洗掉末尾最后一個元素
- 進行向下調整演算法，建成堆
void pop()
{
//交換
swap(con[0], con[con.size() - 1]);
con.pop_back();
shiftDown();
}
top()、size()、empty()
都直接使用容器中的介面實作
T& top()
{
return con.front();
}
size_t size() const
{
return con.size();
}
bool empty() const
{
return con.empty();
}
測驗結果：
但是我們的實作非常的死板，首先是不能創建最小優先級佇列，其次是不能像底層實作一樣，可以選擇多種容器來存盤資料來實作，
解決普通的優先級佇列的兩個問題
解決只能通過vector< T >來存盤資料的問題
我們可以通過容器多添加一個泛型來解決多種容器的存盤
priority_queue可以通過 vector< T >、deque< T >實作
默認使用vector< T >
原因：
- list不支持隨機訪問迭代器的方式來訪問元素
- 與deque相比：deque隨機訪問效率低于vector
與之前代碼需要修改的地方
1、泛型
template<class T, class Container = vector<T>>
2、所需要的容器
private:
Container con;
解決只能創建最大優先級佇列問題
解決辦法，加入新的泛型，該泛型是一個偽函式
如果不知道什么是偽函式，可以看看什么是偽函式，以及偽函式的使用
大小堆創建的不同其實就是在實作向上調整和向下調整時元素比較的不同而已，
與之前代碼需要修改的地方
1、需要創建兩個仿函式類
//用大最小優先級佇列
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
//用于最小優先級佇列
template<class T>
struct Greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
2、加入新泛型
template<class T, class Container = vector<T>, class Compare = Less<T>>
private:
Compare cmp;
3、利用仿函式，替代代碼中關鍵的比較的地方
測驗結果：
完整代碼
//用大最小優先級佇列
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
//用于最小優先級佇列
template<class T>
struct Greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
template<class T, class Container = vector<T>, class Compare = Less<T>>
class PriorityQueue
{
public:
//向下調整
void shiftDown()
{
int parent = 0;
int child = 2 * parent + 1;
while (child < con.size())
{
if (child + 1 < con.size() && cmp(con[child], con[child + 1]))
{
++child;
}
if (cmp(con[parent], con[child]))
{
swap(con[parent], con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//向上調整
void shiftUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (cmp(con[parent], con[child]))
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& val)
{
//尾插
con.push_back(val);
shiftUp(con.size() - 1);
}
void pop()
{
//交換
swap(con[0], con[con.size() - 1]);
con.pop_back();
shiftDown();
}
T& top()
{
return con.front();
}
size_t size() const
{
return con.size();
}
bool empty() const
{
return con.empty();
}
private:
Container con;
Compare cmp;
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278403.html
標籤：AI