- 定义：在计算机科学中，优先队列是一种抽象的数据类型(ADT)，类似于普通队列或堆栈数据结构，但是每个元素都有一个与其相关联的“优先级”。在优先级队列中，高优先级的元素先于低优先级的元素。
在某些实现中，如果两个元素具有相同的优先级，则根据它们入列的顺序为它们提供服务，而在其他实现中，具有相同优先级的元素的顺序是未定义的。
虽然优先级队列通常是用堆实现的，但它们在概念上与堆是不同的。优先队列是一个抽象概念，如list或map，正如list可以用链表或数组实现一样，优先队列也可以用堆（heap）或其他各种方法(如无序数组（unordered array）)实现。
-
常用操作：
is_empty:检查队列是否没有元素。
insert_with_priority:向队列中添加一个具有关联优先级的元素。
pull_highest_priority_element:从具有最高优先级的队列中删除元素，并返回它。
peek:(在此上下文中通常称为find-max或find-min)，它返回最高优先级的元素，但不修改队列，实现得非常频繁，几乎总是在时间内执行。这个操作及其
clear: 清空队列。 -
通常的实现：优先级队列通常使用
heap作为其主干，为插入和删除提供性能，并在初始构建时提供
性能。基本堆数据结构的变体，如配对堆(
pairing heaps)或Fibonacci堆(Fibonacci heaps)，可以为某些操作提供更好的边界。
C++STL中的队列queue
- 操作：
1、入队push:
1 queue<string> q;
2 q.push("Hello World!");
3 q.push("China");
4 cout<<q.front()<<endl;
输出：Hello World！
2、出队pop:
1 queue<string> q;
2 q.push("Hello World!");
3 q.push("China");
4 q.pop();
5 cout<<q.front()<<endl;
输出：China（因为Hello World！已经被除掉了）
3、大小size:返回队列中元素的个数，返回值类型为unsigned int
1 queue<string> q;
2 cout<<q.size()<<" ";
3 q.push("Hello World!");
4 q.push("China");
5 cout<<q.size()<<endl;
输出：0 2（即输出队列中元素的个数）
4、判断队列是否为空empty: 当队列空时，返回true：
1 queue<string> q;
2 cout<<q.empty()<<" ";
3 q.push("Hello World!");
4 q.push("China");
5 cout<<q.empty()<<endl;
输出：1 0（一开始队列是空的，后来插入了两个元素）
5、访问队首元素front:
返回值为队列中的第一个元素，也就是最早、最先进入队列的元素。注意这里只是返回最早进入的元素，并没有把它剔除出队列：
1 queue<string> q;
2 q.push("Hello World!");
3 q.push("China");
4 cout<<q.front()<<" ";
5 q.pop();
6 cout<<q.front()<<endl;
输出：Hello World! China
6、访问队尾元素back:返回队列中最后一个元素，也就是最晚进去的元素：
1 queue<string> q;
2 q.push("Hello World!");
3 q.push("China");
4 cout<<q.back()<<endl;
输出：China（因为它是最后进去的）这里back仅仅是返回最后一个元素，也并没有将该元素从队列剔除掉
C++STL中的priority_queue
- STL中的它：首先函数在头文件
<queue>中，归属于命名空间std。
两种常用的声明方式：
std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;
STL中的对应声明：
template<class _Ty,
class _Container = vector<_Ty>,
class _Pr = less<typename _Container::value_type> >
class priority_queue
默认模板有三个参数，第一个是优先队列处理的类，第二个参数比较有特点，是容纳优先队列的容器，这个容器默认是vector。第三个参数比较重要，支持一个比较结构，默认是less，默认情况下，会选择第一个参数决定的类的<运算符来做这个比较函数。
虽然用的是less结构，然而，队列的出队顺序却是greater的先出！就是说，这里这个参数其实很傲娇，表示的意思是如果!cmp。
自定义优先队列的例子：
struct cmp
{
bool operator()(int &a, int &b) const
{
//因为优先出列判定为!cmp，所以反向定义实现最小值优先
return d[a] > d[b];
}
};
std::priority_queue<int, std::vector<int>, cmp> pq;
c++实现自己的优先队列（顺便囊括了最大堆、堆排序。）
头文件实现：（）
//
// Created by ZC on 2019-08-06.
//
#ifndef ALGORITHM_PRIORITYQUEUE_H
#define ALGORITHM_PRIORITYQUEUE_H
#include <cstdio>
#include <vector>
#include<iostream>
template <typename elemType>
class PriorityQueue {
public:
//单参数构造函数
explicit PriorityQueue(const std::vector<elemType> &t): arr(t)
{
std::cout<<"arr size: "<< Size() << std::endl;
BuildMaxHeap();
std::cout<< "default1" << std::endl;
}
PriorityQueue() = default;
//插入：类似于插入排序，从当前节点当跟节点的路径上，为新增的关键字寻找恰当的位置；
void push(const elemType &elem)
{
arr.push_back(elem);
int position = Size()-1;
// position不能等于0，不然会报错
while((position>0) && arr[Parent(position)] < arr[position])
{
std::swap(arr[Parent(position)], arr[position]);
position = Parent(position);
}
};
//弹出
void pop();
//大小
std::size_t Size(){return arr.size();}
//查看优先级最大的元素
elemType front();
//查看优先级最低的元素
elemType back();
//是否空队列
bool empty(){return !Size();}
void Show();
std::size_t Parent(const std::size_t &);
void HeapSort();
protected:
std::size_t Left(const std::size_t &);
std::size_t Right(const std::size_t &);
void MaxHeapify(const std::size_t &);
void MaxHeapify(const std::size_t &, const std::size_t &);
void BuildMaxHeap();
// undo MinusHeap
// void MinHeapify(const );
private:
std::vector<elemType> arr;
};
#endif //ALGORITHM_PRIORITYQUEUE_H
cpp文件：
//
// Created by ZC on 2019-08-06.
//
#include "PriorityQueue.h"
#include<iostream>
#include<vector>
using namespace std;
//弹出优先级最大的元素
template <typename elemType>
void PriorityQueue<elemType>::pop()
{
if (empty())
std::cout << "pop error!"<< endl;
else
{
std::swap(arr[0], arr[Size()-1]);
arr.pop_back();
MaxHeapify(0);
}
}
template <typename elemType>
elemType PriorityQueue<elemType>::front()
{
if(Size() == 0)
std::cout << "front error!" << std::endl;
else
return arr.front();
}
template <typename elemType>
elemType PriorityQueue<elemType>::back()
{
if (Size()==0)
std::cout << "back error!" << endl;
else
return arr.back();
}
template <typename elemType>
std::size_t PriorityQueue<elemType>::Left(const std::size_t &position)
{
return position * 2 + 1;
}
template <typename elemType>
std::size_t PriorityQueue<elemType>::Right(const std::size_t &position)
{
return position * 2 + 2;
}
template <typename elemType>
std::size_t PriorityQueue<elemType>::Parent(const std::size_t &position)
{
return (position-1) / 2;
}
template <typename elemType>
void PriorityQueue<elemType>::Show()
{
if (empty())
std::cout<< "No elements" << std::endl;
for (auto i: arr)
std::cout << i << " ";
std::cout<<std::endl;
}
//维护堆的性质:该函数的先决条件是position的左右二叉树已经满足堆的性质，这里是最大堆性质；
template <typename elemType>
void PriorityQueue<elemType>::MaxHeapify(const std::size_t &position)
/*
Params:
position: Heaping target node position;
*/
{
std::size_t left = Left(position);
std::size_t right = Right(position);
std::size_t largest=0;
if (left<Size() && arr[left] > arr[position]) //确保在范围内，且维持最大堆形态
largest = left;
else
largest = position;
if (right<Size() && arr[right] > arr[largest]) //找最大元素的位置
largest = right;
if (largest != position)
{
std::swap(arr[largest], arr[position]); //去该去的位置呆着
MaxHeapify(largest); // 递归送他走
}
}
//For Heap sort.
template <typename elemType>
void PriorityQueue<elemType>::MaxHeapify(const std::size_t &position,const std::size_t &d)
/*
Params:
position: Heaping target node position;
size: downgrade size of arr;
*/
{
//
std::size_t left = Left(position);
std::size_t right = Right(position);
std::size_t largest;
if (left<d && arr[left] > arr[position]) //确保在范围内，且维持最大堆形态
largest = left;
else
largest = position;
if (right<d && arr[right] > arr[largest]) //找最大元素的位置
largest = right;
if (largest != position)
{
std::swap(arr[largest], arr[position]); //去该去的位置呆着
MaxHeapify(largest, d); // 递归送他走
}
}
//建立一个堆 : 子树组arr([n/2]+1,...,n)中的元素都是树的叶节点，因此从[n/2],...,1逐个使得满足最大堆性质；
//到0位置时在末尾已经满足；
template <typename elemType>
void PriorityQueue<elemType>::BuildMaxHeap()
{
// 这里的不能写auto或者size_t，因为是无符号，一直等于0，不会被减为0，直接死循环
for(int i=Size()/2; i>=0; --i)
{
MaxHeapify(i);
}
}
template <typename elemType>
void PriorityQueue<elemType>::HeapSort()
{
int length = Size();
for (int i=Size()-1; i>0; --i)
{
std::swap(arr[i], arr[0]);
//每次排序好一个，最大下标递减
--length;
MaxHeapify(0, length);
}
}
int main()
{
//16元素需要调整
vector<int> ivec={4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
PriorityQueue<int> test;
PriorityQueue<int> vtest(ivec);
cout << "-----Test heap properties------ " << endl;
vtest.Show();
cout << "-----Test Priority Queue ------" << endl;
auto largeIterm = vtest.front();
auto lowestIterm = vtest.back();
auto parent1 = vtest.Parent(1);
cout << "largest priority elems is : " << largeIterm << endl;
cout << "lowest priority elems is : " << lowestIterm << endl;
cout << "parent position of 1 is : " << parent1 << endl;
vtest.push(20);
cout << "Priority Queue after insert elems 20 is : ";
vtest.Show();
cout << "Priority Queue after pop max Priority elem is : ";
vtest.pop();
vtest.Show();
cout << "Heap sort after pop largest elems : " << endl;
vtest.HeapSort();
vtest.Show();
}
结果如下：
arr size: 10
default1
-----Test heap properties------
16 14 10 8 7 9 3 2 4 1
-----Test Priority Queue ------
largest priority elems is : 16
lowest priority elems is : 1
parent position of 1 is : 0
Priority Queue after insert elems 20 is : 20 16 10 8 14 9 3 2 4 1 7
Priority Queue after pop max Priority elem is : 16 14 10 8 7 9 3 2 4 1
Heap sort after pop largest elems :
1 2 3 4 7 8 9 10 14 16
Process finished with exit code 0
后记
- 堆排序与插入排序相同，但不同于归并排序，堆排序具有空间原址性：任何时候只需要常数个额外的元素空间存储临时数据；堆排序与归并排序相同，但不同与插入排序，时间复杂度是
。
- 在一个包含
个元素的堆中，所有优先队列的操作都可以在
时间内完成。
- Reference：
- 算法导论
- wikipedia
- 谈C++ STL中的优先队列(priority_queue)
- 队列queue的使用
- 深入理解Java PriorityQueue
网友评论