PriorityQueue

• 定义：在计算机科学中，优先队列是一种抽象的数据类型(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