C++——priority_queue类的模拟实现

什么是优先队列？

在计算机科学中，**优先队列（Priority Queue）**是一种特殊的数据结构，它能够保证每次从队列中取出的元素都是具有最高（或最低）优先级的元素。

优先队列的功能

插入元素：通过使用成员函数push()，可以将一个元素插入到优先级队列中。插入操作会根据元素的优先级进行排序，保证队列中的元素始终按照优先级从高到低的顺序排列。

//插入元素
void push(const T& x)
{
    //将元素插入到底层容器c的尾部
    //并通过std::push_heap函数将元素重新调整到合适的位置，以保持堆的性质。
    c.push_back(x);
    std::push_heap(c.begin(), c.end(), comp);
}
1
2
3
4
5
6
7
8

访问元素：通过使用成员函数top()，可以获取当前优先级最高的元素，而不会改变队列的内容。这样可以方便地查看队列中的最高优先级元素。

//返回队列的首元素
T& top()  
{
    return c.front(); 
}
1
2
3
4
5

删除元素：通过使用成员函数pop()，可以删除当前优先级最高的元素。删除操作会重新调整队列中元素的顺序，确保下一个最高优先级元素能够被访问到。

//删除元素
void pop()
{
    //通过std::pop_heap函数将首元素和尾元素互换位置
    //并通过c.pop_back()删除尾元素，最后使得底层容器c仍然保持堆的性质。
    std::pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
}
1
2
3
4
5
6
7
8

大小和判空：通过使用成员函数size()，可以获取当前队列中的元素个数；使用成员函数empty()，可以判断队列是否为空。

//判断是否为空
bool empty() const 
{
    return c.empty(); 
}
//返回元素的个数
size_t size() const 
{
    return c.size(); 
}
1
2
3
4
5
6
7
8
9
10

完整代码【实现+测试】

#include 
#include 
#include
#include
#include 
using namespace std;
namespace bit
{
    //T为元素类型
    //Container为底层容器类型，默认为vector
    //Compare为比较函数类型，默认为less
    template <class T, class Container = std::vector<T>, class Compare = std::less<T> >
    class priority_queue
    {
    public:
        //默认构造函数，什么也不做
        priority_queue() {}

        //接受两个迭代器参数的构造函数
        //用于将一个范围内的元素插入到priority_queue中
        // 并在构造完成后通过make_heap函数将元素堆化
        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            c.insert(c.end(), first, last);
            std::make_heap(c.begin(), c.end(), comp);
        }
        //判断是否为空
        bool empty() const 
        {
            return c.empty(); 
        }
        //返回元素的个数
        size_t size() const 
        {
            return c.size(); 
        }
        //返回队列的首元素
        T& top()  
        {
            return c.front(); 
        }
        //插入元素
        void push(const T& x)
        {
            //将元素插入到底层容器c的尾部
            //并通过std::push_heap函数将元素重新调整到合适的位置，以保持堆的性质。
            c.push_back(x);
            std::push_heap(c.begin(), c.end(), comp);
        }
        //删除元素
        void pop()
        {
            //通过std::pop_heap函数将首元素和尾元素互换位置
            //并通过c.pop_back()删除尾元素，最后使得底层容器c仍然保持堆的性质。
            std::pop_heap(c.begin(), c.end(), comp);
            c.pop_back();
        }

    private:
        //Container类型的成员变量c，用于存储元素
        Container c;
        //Compare类型的成员变量comp，用于比较元素的优先级
        Compare comp;
    };
}

int main()
{
    //元素按从大到小的顺序排列
    bit::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(3);
    pq.push(55);
    pq.push(1);
    pq.push(2);
    pq.push(5);
	//当priority_queue不为空时，依次输出pq.top()的值，并通过pq.pop()方法删除该元素
    while (!pq.empty())
    {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87