【c++】模拟实现优先级队列（priority_queue）

全部代码

• 以容器适配器的玩法来实现，底层容器默认为vector

• 使用了模板参数T表示存储在队列中的元素类型，Container表示底层容器类型，默认为vector，Compare表示比较器类型，默认为less。

• adjustDown函数用于向下调整堆，保持堆的性质。它从指定的父节点开始，将其与子节点进行比较，如果子节点的值更大，则交换父节点和子节点的位置，并继续向下调整直到满足堆的性质。

• adjustUp函数用于向上调整堆，保持堆的性质。它从指定的子节点开始，将其与父节点进行比较，如果子节点的值更大，则交换父节点和子节点的位置，并继续向上调整直到满足堆的性质。

• 构造函数可以接受一个迭代器范围[first, last]，用于初始化优先队列。在构造过程中，首先将迭代器范围内的元素存储到底层容器中，然后从最后一个非叶子节点开始，依次调用adjustDown函数，使得整个容器满足堆的性质。

• empty函数用于判断优先队列是否为空，即底层容器是否为空。

• size函数用于返回优先队列中元素的个数，即底层容器的大小。

• top函数用于返回优先队列中的最大元素（根节点），但并不删除该元素。

• push函数用于将一个元素插入到优先队列中。它将元素添加到底层容器的末尾，并调用adjustUp函数向上调整堆。

• pop函数用于删除优先队列中的最大元素（根节点）。它首先将根节点与最后一个叶子节点交换位置，然后删除最后一个叶子节点，并调用adjustDown函数向下调整堆。

#pragma once
#include<vector>
namespace hqj
{
    template <class T, class Container = vector<T>, class Compare = less<T> >
 
    class priority_queue
 
    {
    private:
        void adjustDown(int parent)
        {
            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]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
             
            }
        }
 
        void adjustUp(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;
                }
            }
        }
    public:
 
        priority_queue()
        {}
 
        template <class InputIterator>
 
        priority_queue(InputIterator first, InputIterator last)
            :_c(first,last)
        {
            for (int i = _c.size() - 1 - 1; i >= 0; i++)
            {
                adjustDown(i);
            }
        }
 
        bool empty() const
        {
            return _c.empty();
        }
 
        size_t size() const
        {
            return _c.size();
        }
 
        T& top() const
        {
            return (T&)_c.front();
        }
 
        void push(const T& x)
        {
            _c.push_back(x);
            adjustUp(_c.size() - 1);
        }
 
        void pop()
        {
            swap(_c.front(), _c.back());
            _c.pop_back();
            adjustDown(0);
        }
 
    private:
 
        Container _c;
 
        Compare _comp;
 
    };
 
};

私有成员

• _c容器对象:缺省的容器类型是vector

• _comp比较器对象

Container _c;
Compare _comp;

构造函数

• 由于我们模拟实现的优先级队列是一个容器适配器，私有成员中不含内置类型。利用系统生成的默认构造函数特性，会自动调用私有成员的构造函数，所以我们可以不写该优先级队列的构造函数的内容

 priority_queue()
      {}

析构函数

• 同理根据系统默认生成的析构函数特性，当对象销毁时会自动调用自定义类型的析构函数，我们也可以不写

向下调整函数

• 向下调整函数的参数是父节点的下标

• 首先我们通过父亲下标找到其左孩子

• 随后我们通过比较左右孩子大小来确定父亲要与哪个孩子进行比较、交换，至于是选择较大孩子还是较小孩子要根据比较器_comp的返回值来确定，如果我们想建小堆则选取较小的孩子；若我们要建大堆，则选取较大的孩子

• 交换父亲和孩子，并且更新父亲和孩子

• 由于向下调整次数不一定唯一，我们需要用到while结构，循环终止条件为：child下标越界、父子间的大小关系不满足比较器的要求。

 void adjustDown(int parent)
      {
          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]);
                  parent = child;
                  child = parent * 2 + 1;
              }
              else
              {
                  break;
              }
           
          }
      }

向上调整函数

• 向上调整函数的参数是孩子的下标

• 首先通过孩子的下标找到父亲的下标

• 当父子关系满足比较器_comp的要求时进行调整，交换父亲和孩子，并更新父亲和孩子的下标

• 同样，向上调整不止一次，需要用到while结构，循环终止条件为：孩子为根节点、父亲和孩子间的大小关系不满足比较器_comp要求

  void adjustUp(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;
              }
          }
      }

迭代器构造函数

• 由于模拟实现的优先级队列是容器适配器，直接使用底层容器的迭代器构造就行了，读入要建堆的数据

• 都读入后，先找到最后一个叶子节点的父亲节点，随后传递该节点下标进向下调整函数，开始依次向下调整

• 以arr数组为例：

  

   priority_queue(InputIterator first, InputIterator last)
          :_c(first,last)
      {
          for (int i = _c.size() - 1 - 1; i >= 0; i--)
          {
              adjustDown(i);
          }
      }

empty函数

• 还是底层容器接口的复用，调用底层容器的empty函数

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

size函数

• 底层容器接口的复用，调用底层容器的size函数

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

top函数

• 函数作用是返回优先级队列队头元素（也就是堆顶元素），而该元素正好是底层容器的首元素，复用front接口就行，记得要强转

     T& top() const
     {
         return (T&)_c.front();
     }

push函数的实现

• 调用底层容器的push_back函数实现插入功能，然后再进行向上调整堆

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

pop函数的实现

• 首先交换队头元素和队尾元素（堆顶元素和堆尾元素）

• 将队尾元素删除

• 从堆顶开始向下调整堆

      void pop()
      {
          swap(_c.front(), _c.back());
          _c.pop_back();
          adjustDown(0);
      }