【C++】优先级队列介绍与模拟实现

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

💥个人主页：大耳朵土土垚的博客

💥 所属专栏：C++入门至进阶

这里将会不定期更新有关C++的内容，希望大家多多点赞关注收藏💖💖

目录

• 💞💞 前言
• 1.什么是优先级队列
• 2.仿函数的介绍
• 3.优先级队列使用
• 4.优先级队列模拟实现
• • ✨堆向下调整算法
  • ✨堆向上调整算法
  • ✨仿函数
  • ✨优先级队列模拟实现
  • ✨测试代码
  • 5.结语

    1.什么是优先级队列

    优先级队列是一种特殊的队列，其中的元素都被赋予了优先级。元素的优先级决定了它们在队列中的顺序。在优先级队列中，元素按照优先级从高到低的顺序出队列。

    优先级队列可以通过不同的数据结构来实现，常用的有二叉堆、二叉搜索树和斐波那契堆等。

    优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

    2.仿函数的介绍

    仿函数（Functor）是一种重载了函数调用运算符()的类或结构体，它可以像函数一样被调用。通过重载函数调用运算符，仿函数可以实现自定义的操作行为。

    仿函数可以像普通函数一样接受参数，并返回结果。它可以用于函数对象的传递、函数指针的替代、算法的灵活性增加等场景。

    使用仿函数的步骤如下：

    1. 定义一个仿函数类或结构体，重载函数调用运算符()。可以根据需要定义构造函数、析构函数和其他成员函数。
    2. 在代码中创建仿函数对象。仿函数对象可以像函数一样调用，传入参数，并返回结果。

    下面是一个示例，演示了使用仿函数实现求平方的功能：

    // 定义仿函数类
    struct Square {
        int operator()(int x) const {
            return x * x;
        }
    };
    int main() {
        Square square;  // 创建仿函数对象
        int result = square(5);  // 调用仿函数
        // result = 25
        return 0;
    }
    

    在上述示例中，Square 是一个仿函数类，重载了函数调用运算符()。通过创建 Square 对象 square，并像函数一样调用

    square(5)，可以得到5的平方值25。

    通过仿函数，我们可以实现更灵活和自定义的操作行为，并且可以与STL算法等标准库函数配合使用，提高代码的可读性和可维护性。

    3.优先级队列使用

    函数声明	接口说明
    priority_queue()/priority_queue(first,last)	构造一个优先级队列
    empty( )	检测优先级队列是否为空，是返回true，否则返回false
    top( )	返回优先级队列中最大(最小元素)，即堆顶元素
    push(x)	在优先级队列中插入元素x
    pop()	删除优先级队列中最大(最小)元素，即堆顶元素

    测试代码如下：

    #define _CRT_SECURE_NO_WARNINGS 1
    #include
    using namespace std;
    #include
    #include 
    #include  // greater算法的头文件
    void TestPriorityQueue()
    {
    	// 默认情况下，创建的是大堆
    	vector v = { 3,2,7,6,0,4,1,9,8,5 };
    	priority_queue q1;
    	//使用范围for入队列
    	for (auto& e : v)
    		q1.push(e);
    	while (!q1.empty())
    	{
    		cout 
    		cout 
    	TestPriorityQueue();
    	return 0;
    }
    
            bool operator()(const T& x, const T& y)
            {
                return x = 0; i--)
                {
                    Adjust_Down(i);
                }
            }
            //initializer_list构造
            priority_queue(initializer_list il)
            {
                for (const auto& e : il)
                {
                    _c.push_back(e);
                }
                //调整数据为堆
                for (int i = ((int)_c.size() - 1-1)/2; i >= 0; i--)
                {
                    Adjust_Down(i);
                }
            }
            //向上调整算法
            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& val)
            {
                _c.push_back(val);
                Adjust_Up(_c.size() - 1);
            }
            //向下调整算法
            void Adjust_Down(int parent)
            {
                int child = parent * 2 + 1;
                while (parent