C++：priority_queue（优先级队列）的模拟实现

目录

一、什么是优先级队列

二、优先级队列的定义

三、优先级队列的常用接口

四、模拟实现一个优先级队列

1、posh接口 

2、empty接口、size接口和top接口

3、pop接口

4、构造函数

五、整体代码

一、什么是优先级队列

        首先优先级队列不是队列，C++ 中的优先队列是STL中的派生容器。当你往优先级队列里存放数据的时候，它会像堆一样存放数据，将最大的数据或最小的数据放到前面。

（至于什么是堆可以看这篇文章->堆的实现）

二、优先级队列的定义

其中：

T 是数据的类型；

Container 是容器类型，vector<T> 是容器；

Compare 是作为仿函数容器，决定了是最大的数据还是最小的数据放在前面。

三、优先级队列的常用接口

四、模拟实现一个优先级队列

        （以大堆为例）

        我们要实现一个优先级队列，最开始要搭建好它的底层。

template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:

private:
    Container c;
    Compare comp;
};

用 vector<T> 作为容器（或者其它），构建一个自变量 c，同理用 liss<T>作为容器，构建仿函数comp。

因为优先级队列会像堆一样存放数据，所以实现优先级队列基本就是实现一个堆。

1、posh接口 

• 若我们向一个堆里存放数据后，需要向上调整，所以需要一个向上调整数据的函数 adjust_up()

 (注：在标准库里有adjust_up()函数，但我们是要自己完成一个)

void adjust_up(int child)
{
    int parent = (child - 1) / 2;

    while (child > 0)
    {
        if (c[parent] < c[child])
        {
            swap(c[parent], c[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

但这个代码不够好，（事先说明下面还有一个向下调整函数）若我们想用小堆嘞？总不可能要在类里一个个改它们的比较方式吧，这时候仿函数就该英雄出场了。

if (c[parent] < c[child]) -> if (comp(c[parent], c[child]))

将if中的判断改为函数判断的形式，我们只需在判断函数里修改即可。 

所以push接口可以写成这样↓

void push(const T& x)
{
    c.push_back(x);
    adjust_up(c.size() - 1);
}

2、empty接口、size接口和top接口

因为我们借用了vector作为容器，所以我们可以使用它的接口来代替优先级队列的接口。

bool empty() const
{
    return c.empty();
}

size_t size() const
{
    return c.size();
}

size_t size() const
{
    return c.size();
}

3、pop接口

当我们要删除数据的时候删堆顶的数据，要将堆顶的数据和堆最后的数据互换，然后在利用容器的接口来删除数据。

void pop()
{
    swap(c[0],c[c.size() - 1]);
    c.pop_back();
    adjush_dowm();
}

• 这里我们需要利用向下调整函数adjust_down()将优先级队列重新排好序。 

void adjush_dowm()
{
    int parent = 0;
    int child = parent * 2 + 1;

    while (child < c.size())
    {
        if (child + 1 < c.size() && comp(c[child], c[child + 1]))
        {
            child++;
        }

        if (comp(c[parent], c[child]))
        {
            swap(c[parent], c[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

 这样我们的优先级队列的大部分接口就实现了。现在我们还差它的构造函数了。

4、构造函数

priority_queue() {};
//利用迭代器来构造优先级队列
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
    InputIterator it = first;
    while (it != last)
    {
        push(*it);
        it++;
    }
}

五、整体代码

template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:
    priority_queue() {};
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
    {
        InputIterator it = first;
        while (it != last)
        {
            push(*it);
            it++;
        }
    }

    void adjust_up(int child)
    {
        int parent = (child - 1) / 2;

        while (child > 0)
        {
            if (comp(c[parent], c[child]))
            {
                swap(c[parent], c[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
                break;
        }
    }

    void push(const T& x)
    {
        c.push_back(x);
        adjust_up(c.size() - 1);
    }

    bool empty() const
    {
        return c.empty();
    }

    size_t size() const
    {
        return c.size();
    }

    const T& top() const
    {
        return c[0];
    }

    void adjush_dowm()
    {
        int parent = 0;
        int child = parent * 2 + 1;

        while (child < c.size())
        {
            if (child + 1 < c.size() && comp(c[child], c[child + 1]))
            {
                child++;
            }

            if (comp(c[parent], c[child]))
            {
                swap(c[parent], c[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
                break;
        }
    }

    void pop()
    {
        swap(c[0],c[c.size() - 1]);
        c.pop_back();
        adjush_dowm();
    }

    private:
        Container c;
        Compare comp;
    };