优先队列：索引最小优先队列（c++11）、最小优先队列、最大优先队列
文章目录
前言
最大优先队列和最小优先队列，他们可以分别快速访问到队列中的最大元素和最小元素，但是他们有一个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们，而索引最小优先队列和索引最大优先队列可以解决这一问题，这里拿索引最小优先队列举例：
一、索引最小优先队列的实现思路
1.1 步骤一：
- 存储数据时，给每一个数据元素关联一个整数，例如insert(int k, T t)，可以看做k是t关联的整数，那么我们的实现需要通过k这个值，快速获取到队列中t这个元素，因此k具有唯一性。
1.2 步骤二：
- 步骤一完以后的结果，虽然我们给每个元素关联了一个整数，并且可以使用这个整数快速获取到该元素，但是，items数组中的元素顺序是随机的，并不是堆有序的，所以，可以增加一个int类型数组pq来保存每个元素在items数组中的索引，pq数组需要堆有序，即对pq数据进行修改，符合堆的标准。
堆有序：items[pq[i]]小于等于items[pq[2i]]和items[pq[2i+1]]
1.3 步骤三
- 通过步骤二，我们发现，可以通过上浮算法和下沉算法做堆调整的时候，其实调整的是pq数组。如果需要对items中的元素进行修改，比如让items[0]=‘H’，就需要对pq中的数据做堆调整，而且是调整pq[9]中元素的位置，但是就会遇到一个问题，修改的是items数组中0索引处的值，如何才能快速的知道需要挑中pq[9]中元素的位置呢？
最直观的想法是遍历pq数组，拿出每一个元素和o做比较，但效率很低。 因此，可以另外增加一个数组qp，vector qp
用来存储pq的逆序。 在pq数组中：pq[1] = 6; 那么在qp数组中，把6作为索引，1作为值；即 qp[6] = 1;
当有了pq数组后，如果我们修改了items[0]=‘A’，那么久可以先通过索引0，在qp数组中找到qp的索引，qp[0]=9，那么直接调整pq[9]即可。
二、索引最小优先队列的API设计
三、索引最小优先队列代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//最大索引优先队列可根据最小索引优先队列去写
template<class T>
class IndexMinPriorityQueue
{
public:
IndexMinPriorityQueue(int capacity); // 创建容量为capacity的IndexMinPriorityQueue对象
//获取队列中元素的个数
int size();
//判断队列是否为空
bool isEmpty();
//判断堆中索引i处和j处元素的大小
bool less(int i, int j);
//交换堆中i索引和j索引处的值
void exch(int i, int j);
// 判断k对应的元素是否存在
bool contains(int k);
//最小元素关联的索引
int minIndex();
//往队列中插入一个元素，并关联索引
void insert(int i, T t);
// 上浮算法
void swim(int k);
//删除队列中最小的元素，并返回该元素关联的索引
int delMin();
// 删除索引i处关联的元素
void del(int i);
//把与索引i关联的元素修改为t
void changeItem(int i, T t);
// 下浮算法
void sink(int k);
void display();
~IndexMinPriorityQueue();
protected:
private:
vector<T>* items = nullptr; // 用来存储元素的数组
vector<int>* pq = nullptr; // 保存每个元素在items数组中的索引，pq数组需要堆有序
vector<int>* qp = nullptr; // 保存qp的逆序，pq的值作为索引，pq的索引作为值
int len; // 记录堆中元素的个数
};
template<class T>
IndexMinPriorityQueue<T>::IndexMinPriorityQueue(int capacity) {
this->items = new vector<T>;
items->resize(capacity + 1);
this->pq = new vector<int>(capacity + 1, -1);
this->qp = new vector<int>(capacity + 1, -1);
this->len = 0;
}
template<class T>
int IndexMinPriorityQueue<T>::size() {
return len;
}
template<class T>
bool IndexMinPriorityQueue<T>::isEmpty() {
return len == 0;
}
template<class T>
bool IndexMinPriorityQueue<T>::less(int i, int j) {
return items->at(pq->at(i)) < items->at(pq->at(j));
}
template<class T>
void IndexMinPriorityQueue<T>::exch(int i, int j) {
// 交换pq中的数据
int temp = pq->at(i);
pq->at(i) = pq->at(j);
pq->at(j) = temp;
// 更新qp中的数据
qp->at(pq->at(i)) = i;
qp->at(pq->at(j)) = j;
}
template<class T>
bool IndexMinPriorityQueue<T>::contains(int k) {
return qp->at(k) != -1;
}
template<class T>
int IndexMinPriorityQueue<T>::minIndex() {
return pq->at(1);
}
template<class T>
void IndexMinPriorityQueue<T>::insert(int i, T t) {
//判断i是否已经被关联，如果已经被关联，则不让插入
if (contains(i))
{
return;
}
// 元素个数+1
len++;
//把数据存储到item对应的i位置处
items->at(i) = t;
// 把i存储到pq中
pq->at(len) = i;
//通过qp来记录pq中的i
qp->at(i) = len;
// 通过上浮完成堆的调整
swim(len);
}
template<class T>
int IndexMinPriorityQueue<T>::delMin() {
//获取最小元素关联的索引
int minIndex = pq->at(1);
//交换pq中索引1处和最大索引处的元素
exch(1, len);
//删除qp中对应的内容(置为-1）
int k = pq->at(len);
//qp->erase(qp->begin() + k);
qp->at(k) = -1;
//删除pq最大索引处的内容，置为-1
pq->at(len) = -1;
//删除items中对应的内容(置为空）
T val;
items->at(minIndex) = val;
//元素个数-1
len--;
// 下沉算法
sink(1);
return minIndex;
}
template<class T>
void IndexMinPriorityQueue<T>::del(int i) {
//找到i在pq中的索引
int k = pq->at(i);
// 交换pq中索引k处的值和索引len处的值
exch(k, len);
//删除qp中的内容
qp->at(pq[len]) = -1;
//删除items中的内容
items->erase(items->begin() + k);
// 元素的数量-1
len--;
// 堆的调整（上浮和下沉算法都要执行一次，才能让堆有序）
sink(k);
swim(k);
}
template<class T>
void IndexMinPriorityQueue<T>::changeItem(int i, T t) {
//修改items数组中i位置的元素为t
items->at(i) = t;
//找到i在pq中出现的位置
int k = qp->at(i);
sink(k);
swim(k);
}
template<class T>
void IndexMinPriorityQueue<T>::swim(int k) {
while (k > 1)
{
if (less(k, k / 2))
{
exch(k, k / 2);
}
k = k / 2;
}
}
template<class T>
void IndexMinPriorityQueue<T>::sink(int k) {
while (2 * k <= len)
{
//找到子节点中较小的值
int minIndex;
if (2 * k + 1 <= len)
{
if (less(2 * k, 2 * k + 1))
{
minIndex = 2 * k;
}
else
minIndex = 2 * k + 1;
}
else
minIndex = 2 * k;
//比较当前节点和较小值
if (less(k, minIndex))
{
break;
}
exch(k, minIndex);
k = minIndex;
}
}
template<class T>
void IndexMinPriorityQueue<T>::display() {
cout << "items: ";
for (int i = 0; i < items->size(); i++)
{
cout << items->at(i) << " ";
}
cout << endl;
cout << "pq: ";
for (int i = 0; i < pq->size(); i++)
{
cout << pq->at(i) << " ";
}
cout << endl;
cout << "qp: ";
for (int i = 0; i < qp->size(); i++)
{
cout << qp->at(i) << " ";
}
cout << endl;
}
template<class T>
IndexMinPriorityQueue<T>::~IndexMinPriorityQueue() {
delete items;
delete pq;
delete qp;
items = nullptr;
pq = nullptr;
qp = nullptr;
}
int main()
{
IndexMinPriorityQueue<string> queue(10);
queue.insert(0, "A");
queue.insert(1, "C");
queue.insert(2, "F");
queue.changeItem(2, "B");
queue.display();
while (!queue.isEmpty()) {
int index = queue.delMin();
cout << index << " ";
}
cout << endl;
queue.display();
system("pause");
return 0;
}
五、最小优先队列代码
- 算法原理自行百度或查看数据结构与算法一书
#include <iostream>
#include <string>
using namespace std;
//使用堆实现优先队列(对堆进行排序，取出的永远是队列中的最大值）
//c++11 自带的队列API
//priority_queue<int> p1;//默认情况下是最大值优先队列
//priority_queue<int, vector<int>, less<int>> p2;//最大值优先队列
//priority_queue<int, vector<int>, greater<int>> p3;//最小值优先队列
template<class T>
class MinPriorityQueue
{
public:
MinPriorityQueue(int capacity);
~MinPriorityQueue();
// 获取队列中元素的个数
int size();
//判断队列是否为空
bool isEmpty();
//判断堆中索引i处的元素是否小于索引j处的元素
bool less(int i, int j);
// 交换堆中i索引和j索引处的值
void exch(int i, int j);
//往堆中插入一个元素
void insert(T t);
//删除堆中最大的元素，并返回这个最大元素
T delMix();
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
void swim(int k);
// 使用下浮算法，使索引k处的元素能在堆中处于一个正确的位置
void sink(int k);
protected:
private:
T* items = nullptr;
int len;
};
template<class T>
MinPriorityQueue<T>::MinPriorityQueue(int capacity) {
this->items = new T[capacity + 1]; // 0位置不存储元素
this->len = 0;
}
template<class T>
int MinPriorityQueue<T>::size() {
return len;
}
template<class T>
bool MinPriorityQueue<T>::isEmpty() {
return len == 0;
}
template<class T>
bool MinPriorityQueue<T>::less(int i, int j) {
return items[i] < items[j];
}
template<class T>
void MinPriorityQueue<T>::exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
template<class T>
void MinPriorityQueue<T>::insert(T t) {
items[++len] = t;
swim(len);
}
template<class T>
T MinPriorityQueue<T>::delMix() {
T minData = items[1];
exch(1, len);
T val;
items[len] = val; // 删除元素后置位空
len--;
sink(1);
return minData;
}
template<class T>
void MinPriorityQueue<T>::swim(int k) {
while (k > 1)
{
if (less(k, k / 2))
{
exch(k, k / 2);
}
k = k / 2;
}
}
template<class T>
void MinPriorityQueue<T>::sink(int k) {
while (2 * k <= len)
{
int minIndex;
if (2 * k + 1 <= len)
{
if (less(2 * k, 2 * k + 1))
{
minIndex = 2 * k;
}
else
minIndex = 2 * k + 1;
}
else
minIndex = 2 * k;
if (less(k, minIndex))
{
break;
}
exch(k, minIndex);
k = minIndex;
}
}
template<class T>
MinPriorityQueue<T>::~MinPriorityQueue() {
if (items != nullptr)
{
delete[] items;
items = nullptr;
}
}
int main()
{
MinPriorityQueue<string>* queue = new MinPriorityQueue<string>(10);
queue->insert("A");
queue->insert("B");
queue->insert("C");
queue->insert("D");
queue->insert("E");
queue->insert("F");
queue->insert("G");
while (!queue->isEmpty()) {
string maxData = queue->delMix();
cout << maxData << " ";
}
cout << endl;
delete queue;
system("pause");
return 0;
}
六、最大优先队列代码
- 算法原理自行百度或查看数据结构与算法一书
#include <iostream>
#include <string>
using namespace std;
//使用堆实现优先队列(对堆进行排序，取出的永远是队列中的最大值）
//c++11 自带的队列API
//priority_queue<int> p1;//默认情况下是最大值优先队列
//priority_queue<int, vector<int>, less<int>> p2;//最大值优先队列
//priority_queue<int, vector<int>, greater<int>> p3;//最小值优先队列
template<class T>
class MaxPriorityQueue
{
public:
MaxPriorityQueue(int capacity);
~MaxPriorityQueue();
// 获取队列中元素的个数
int size();
//判断队列是否为空
bool isEmpty();
//判断堆中索引i处的元素是否小于索引j处的元素
bool less(int i, int j);
// 交换堆中i索引和j索引处的值
void exch(int i, int j);
//往堆中插入一个元素
void insert(T t);
//删除堆中最大的元素，并返回这个最大元素
T delMax();
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
void swim(int k);
// 使用下浮算法，使索引k处的元素能在堆中处于一个正确的位置
void sink(int k);
protected:
private:
T* items = nullptr;
int len;
};
template<class T>
MaxPriorityQueue<T>::MaxPriorityQueue(int capacity) {
this->items = new T[capacity + 1]; // 0位置不存储元素
this->len = 0;
}
template<class T>
int MaxPriorityQueue<T>::size() {
return len;
}
template<class T>
bool MaxPriorityQueue<T>::isEmpty() {
return len == 0;
}
template<class T>
bool MaxPriorityQueue<T>::less(int i, int j) {
return items[i] < items[j];
}
template<class T>
void MaxPriorityQueue<T>::exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
template<class T>
void MaxPriorityQueue<T>::insert(T t) {
items[++len] = t;
swim(len);
}
template<class T>
T MaxPriorityQueue<T>::delMax() {
T maxData = items[1];
exch(1, len);
T val;
items[len] = val; // 删除元素后置位空
len--;
sink(1);
return maxData;
}
template<class T>
void MaxPriorityQueue<T>::swim(int k) {
while (k > 1)
{
if (less(k / 2, k))
{
exch(k / 2, k);
}
k = k / 2;
}
}
template<class T>
void MaxPriorityQueue<T>::sink(int k) {
while (2 * k <= len)
{
int maxIndex;
if (2 * k + 1 <= len)
{
if (less(2 * k, 2 * k + 1))
{
maxIndex = 2 * k + 1;
}
else
maxIndex = 2 * k;
}
else
maxIndex = 2 * k;
if (!less(k, maxIndex))
{
break;
}
exch(k, maxIndex);
k = maxIndex;
}
}
template<class T>
MaxPriorityQueue<T>::~MaxPriorityQueue() {
if (items != nullptr)
{
delete[] items;
items = nullptr;
}
}
int main()
{
MaxPriorityQueue<string>* queue = new MaxPriorityQueue<string>(10);
queue->insert("A");
queue->insert("B");
queue->insert("C");
queue->insert("D");
queue->insert("E");
queue->insert("F");
queue->insert("G");
while (!queue->isEmpty()) {
string maxData = queue->delMax();
cout << maxData << " ";
}
cout << endl;
queue->insert("A");
queue->insert("B");
queue->insert("C");
queue->insert("D");
while (!queue->isEmpty()) {
string maxData = queue->delMax();
cout << maxData << " ";
}
cout << endl;
delete queue;
system("pause");
return 0;
}
本文含有隐藏内容，请 开通VIP 后查看