【C++】模拟实现priority_queue(优先级队列)

举报
修修修也 发表于 2024/10/25 15:33:18 2024/10/25
【摘要】 🦄个人主页:修修修也 🎏所属专栏:实战项 目集 ⚙️操作环境:Visual Studio 2022​编辑​目录一 .了解 项 目功能 📌 了解priority_queue官方 标 准 📌 了解模 拟实现 priority_queue 二.逐步 实现项 目功能模 块 及其 逻辑详 解 📌 实现 priority_queue成 员变 量 📌 实现 priority_queue()构造...

🦄个人主:修修修也

🎏所属专栏:实战项 目集

⚙️操作:Visual Studio 2022

​编辑​


.了解 目功能

📌 了解priority_queue官方

📌 了解模 拟实现 priority_queue

二.逐步 实现项 目功能模 及其 逻辑详

📌 实现 priority_queue成 员变

📌 实现 priority_queue()构造函数

🎏 迭代区 构造函数

🎏 无参构造 函数

📌 实现 push()函数

📌 实现 AdjustUp()函数

📌 实现 pop()函数

📌 实现 AdjustDown()函数

📌 实现 top()函数

📌 实现 size()函数

📌 实现 empty()函数

三. 目完整代

📌 test.cpp文件

📌 PriorityQueue.h文件

结语


.了解目功能

📌了解priority_queue官方

       在本次项目中我们的目标是拟实现一个priority_queue,先一起看一下C++标准文档中priority_queue的定义: cplusplus : C++ priority_queue 准文档 https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue ​编辑

        总结一下:

1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。

2. 此上下文似于堆,在堆中可以随插入元素,并且只能索最大堆元素(优先队列中位于顶部的元素)。​编辑

3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

编辑

5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。

6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

7. priority_queue的

        更多有关数据——相关的基础知识可以移步:【数据 构】什么是堆 ? https://blog.csdn.net/weixin_72357342/article/details/134904555         文章目录如下:

编辑


📌了解模拟实现priority_queue

        在本次项目中我们的目标是实现一个priority_queue容器适配器:

        该priority_queue容器适配器底层可以使用vector或deque来实现,但是单独分别使用vector或deque来实现一个堆太过麻烦,我们不如借助模板来一次性实现既可以使用顺序底层的堆,又可以实现deque底层的堆:

        priority_queue提供的功能有:

1. priority_queue迭代区初始化函数

2. push()函数 [ 包括AdjustDowd() 函数 ]

3. pop()函数 [ 包括AdjustUp() 函数 ]

4. top()

5. size()

6. empty()


二.逐步实现项目功能模及其逻辑详

通过第一部分对项目功能的介绍,我们已经对priority_queue的功能有了大致的了解,虽然看似需要实现的功能很多,貌似一时间不知该如何下手,但我们可以分步分模来分析目的流程,最后再将各部分行整合,所以大家不用担心,跟着我一步一步分析吧!


!!!注意,部分的代只是详细某一部分的实现逻辑,故可能会减一些与部分不相关的代以便大家理解,需要看或拷完整详细的朋友可以移步本文第三部分。


📌实现priority_queue员变

        因为priority_queue的底层是用vector或deque来实现的,所以我们只需要一个vector或deque成员变即可.但因为我们选择将priority_queue写成类模板,所以这里成员变量的类型是模板类型.

        其实可以理解为priority_queue的底层就是一个vector或deque,但我们过类的特性,vector或deque一步的封装,使其行符合priority_queue的行,就完成了一个priority_queue.

该部分功能实现代码如下:

namespace mfc

{

    template<class T, class Container = vector<T>, class Comapre = less<T>>

//这里模板的最后一个参数是控制堆模板是排大堆还是小堆的,是一种仿函数

    class priority_queue

    {

    private:

//成员变量和成员函数子函数

Container _con;


    public:

         //成员函数

        

    };

}


📌实现priority_queue()构造函数

🎏迭代区构造函数

        使用一个迭代区间来初始化堆, 其实就是个迭代区的元素拷存入堆中, 再根据堆的特性将些元素建成大堆或小堆即可. 注意, 迭代器的类型有很多种, 我们可以直接将构造函数写成函数模板. 下图是在数据结构堆博客截取的向上建堆的图示过程, 方便大家理解建堆的过程:     

编辑

        综上所述,该部分代码如下:

template<class InputIterator>

priority_queue(InputIterator first, InputIterator last)

{

    while (first != last)

    {

        _con.push_back(*first);//按迭代器顺序将数据插入堆中

        ++first;

    }


    //建堆 (size-1是下标,再-1是最后一个非叶子结点的公式)

    for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)

    {

        AdjustDown(i);//向下调整建堆

    }

}


🎏无参构造函数

        因为我们前面实现了迭代区间初始化构造函数,编译器就不会再生成默的无参构造函数,这样会导致我们如果后续使用默认构造时出现一些问题:​编辑

        因此我们把无参构造函数补充上,代码如下:

priority_queue()

{}


📌实现push()函数

        priority_queue的push()就是在容器尾部插入一个元素,因为底层的vector或deque都实现有尾插函数push_back(),所以我们直接调用就可以,但是直接就在尾部插入的话,堆的.致其不符合大/小的特性,所以我们要将每个新插入的元素向上到合适的位置才可以,代码如下:

void push(const T& x)

{

    _con.push_back(x);

    AdjustUp(_con.size() - 1);//向上调整函数

}


📌实现AdjustUp()函数

        因为我们不能保证新入的元素一定完全符合堆定的要求,为了防止新插入的元素破坏堆的性,因此我们需要新入堆的元素行向上,直到调整到其满足堆排序的性质为止.

        为了方便理解,我们拿刚才的大堆做一下演示,逻辑图如下:​编辑​编辑​编辑

        实现代码如下:

void AdjustUp(int child)

{

    Comapre com;//控制大堆还是小堆的仿函数变量


    size_t parent = (child - 1) / 2;

    while (child > 0)

    {

        if (com(_con[parent], _con[child]))//com会根据仿函数的类型来套用相应的仿函数

        {

            swap(_con[child], _con[parent]);

            child = parent;

            parent = (child - 1) / 2;

        }

        else

        {

            break;

        }

    }

}


📌实现pop()函数

        因为priority_queue的特性使得元素一定当前堆中最大/小的,因此我们堆操作往往需要出的是堆元素.

        但是我们不能直接将堆元素,因为这样致堆中剩下的元素关系全部乱掉:

编辑

        后面剩余的数据也完全不符合大堆/小堆的特性:

编辑

        因此合理的操作出堆就将堆元素和堆尾元素,然后将新堆元素向下整到合适的位置上:

编辑

        代码如下:

void pop()

{

    swap(_con[0], _con[_con.size() - 1]);

    _con.pop_back(); //删掉最后一个元素

    AdjustDown(0); //将堆顶元素(即0号位置元素)向下调整到合适的位置

}


📌实现AdjustDown()函数

        因为我们不能保证换到堆顶的元素一定完全符合堆定的要求,为了防止新上的元素破坏堆的性,因此我们需要上的元素行向下,直到调整到其满足堆排序的性质为止.

        为了方便理解,我们拿刚才的大堆做一下演示,逻辑图如下:

        首先是和堆尾元素:

编辑

        其次将交后的新堆元素和两个孩子做比,如果是大堆,那么只要孩子比新堆元素大,二者就位置,如果两个孩子都比堆元素大,则元素和大的那个孩子交位置:

编辑

        直到向下整到叶子点位置元素比两个孩子点都大停止向下:

编辑

        注意: 向上整我只需要将入堆元素与它的双亲结点比,而向下需要先比点的两个孩子的大小,然后双亲结点与大的/小的(取决于大堆是小堆)孩子交位置,直到将该结点交换至叶子结点或比两个孩子结点都大/小为止.

        代码如下:

void AdjustDown(int parent)

{

    Comapre com;


    //找左右孩子大的那个

    size_t child = parent * 2 + 1;

            

    while (child < _con.size())

    {

        if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//写死就固定是大堆还是小堆了,传模板可以达到自定义的效果

        {

            ++child;

        }


        if (com(_con[parent], _con[child]))

        {

            swap(_con[child], _con[parent]);

            parent = child;

            child = parent * 2 + 1;

        }

        else

        {

            break;

        }

    }

}


📌实现top()函数

        priority_queue的top()函数就是取堆的元素,vector和deque都有重载operator[]函数,我们可以直接调用它来取到堆顶元素,代码如下:

const T& top()

{

    return _con[0];

}


📌实现size()函数

        priority_queue的size()函数同样可以直接调用底层容器的size()函数,代码如下:

size_t size()

{

    return _con.size();

}

📌实现empty()函数

        priority_queue的empty()函数同样可以直接调用底层容器的empty()函数,代码如下:

bool empty()

{

    return _con.empty();

}

📌实现swap()函数

        priority_queue的swap()函数同样可以直接调用库里的swap()函数,代码如下:

void Swap(priority_queue& other)

{

    std::swap(_con, other._con);

}


三.目完整代

        因为模板定和声明不能分离,所以我们将程序运行的代码分别在两个工程文件中编辑,完整代码如下:

📌test.cpp文件

#include<iostream>

#include<vector>

using namespace std;
#include"PriorityQueue.h"
int main()

{

    mfc::test_priority_queue();
    return 0;

}


📌PriorityQueue.h文件

namespace mfc

{

    template<class T, class Container = vector<T>, class Comapre = less<T>>

    class priority_queue

    {

    private:

        void AdjustDown(int parent)

        {

            Comapre com;
            //找左右孩子大的那个

            size_t child = parent * 2 + 1;
            while (child < _con.size())

            {

                if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//写死就固定是大堆还是小堆了,传模板可以达到自定义的效果

                {

                    ++child;

                }
                if (com(_con[parent], _con[child]))

                {

                    swap(_con[child], _con[parent]);

                    parent = child;

                    child = parent * 2 + 1;

                }

                else

                {

                    break;

                }

            }

        }
        void AdjustUp(int child)

        {

            Comapre com;
            size_t parent = (child - 1) / 2;

            while (child > 0)

            {

                if (com(_con[parent], _con[child]))

                {

                    swap(_con[child], _con[parent]);

                    child = parent;

                    parent = (child - 1) / 2;

                }

                else

                {

                    break;

                }

            }

        }
    public:

         priority_queue()

         {}
         template<class InputIterator>

         priority_queue(InputIterator first, InputIterator last)

         {

             while (first != last)

             {

                 _con.push_back(*first);

                 ++first;

             }
             //建堆 (size-1是下标再-1是最后一个非叶子结点的公式)

             for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)

             {

                 AdjustDown(i);

             }
         }

         void push(const T& x)

         {

             _con.push_back(x);

             AdjustUp(_con.size() - 1);

         }

         void pop()

         {

             swap(_con[0], _con[_con.size() - 1]);

             _con.pop_back();

             AdjustDown(0);

         }

        const T& top()

        {

            return _con[0];

        }
        bool empty()

        {

            return _con.empty();

        }
        size_t size()

        {

            return _con.size();

        }
        void Swap(priority_queue& other)

        {

            std::swap(_con, other._con);

        }
    private:

        Container _con;

    };
    void test_priority_queue()

    {

        priority_queue<int,vector<int>,greater<int>> pq;//传greater是小堆,默认是less大堆

        pq.push(3);

        pq.push(1);

        pq.push(5);

        pq.push(7);

        pq.push(2);
        while (!pq.empty())

        {

            cout << pq.top() << " ";

            pq.pop();

        }

        cout << endl;

    }

}

测试结:​编辑


结语

希望priority_queue的模拟实现详解能大家有所帮助,迎大佬留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学,一起!

相关文章推荐

【C++】模 拟实现 queue

【C++】模 拟实现 stack

【C++】模 拟实现 list

【C++】模 拟实现 vector

【C++】 库类 vector

【C++】模 拟实现 string

【C++】构建第一个C++ :Date

【C++】 的六大默 函数及其特性 (万字 )

【C++】什么是 ?


​编辑

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。