585-优先级队列的实现

朴灿烈づ我的快乐病毒、 2022-09-12 02:48 149阅读 0赞

## 优先级队列的实现 ##

**默认是大根堆**

#include <iostream>
    #include <functional>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    
    //优先级队列实现(默认是大根堆)  priority_queue(vector)  push pop top empty size
    class PriorityQueue
    {
        
    public:
        using Comp = function<bool(int, int)>;//定义一个函数对象 
        PriorityQueue(int cap = 20, Comp comp = greater<int>())//构造函数，默认是大根堆，greater是比较大于的 
            : size_(0)
            , cap_(cap)
            , comp_(comp)
        {
        
            que_ = new int[cap_];
        }
    
        PriorityQueue(Comp comp)//构造函数，用户比较方便调用的 
            : size_(0)
            , cap_(20)
            , comp_(comp)
        {
        
            que_ = new int[cap_];
        }
    
        ~PriorityQueue()//析构函数 
        {
        
            delete[]que_;
            que_ = nullptr;
        }
    
    public:
        //入堆操作
        void push(int val)
        {
        
            //判断扩容
            if (size_ == cap_)
            {
        
                int* p = new int[2 * cap_];
                memcpy(p, que_, cap_ * sizeof(int));//因为操作的是整型，所以可以调用这个方法 
                delete[]que_;
                que_ = p;
                cap_ *= 2;
            }
    
            if (size_ == 0)
            {
        
                //只有一个元素，不用进行堆的上浮调整
                que_[size_] = val;
            }
            else
            {
        
                //堆里面有多个元素，需要进行上浮调整
                siftUp(size_, val);
                //从插入的数组的末尾位置调整，size是元素个数，所以刚好是这次要放入元素的下标 
            }
            size_++;//存放完元素后，size++，size代表的是元素的个数，也代表最后一个元素的后继位置 
        }
    
        //出堆操作，出的是堆顶元素 
        void pop()
        {
        
            if (size_ == 0)
                throw "container is empty!";
    
            size_--;//数组下标直接操作-- 
            if (size_ > 0)//如果数组中还有其他元素 
            {
        
                //删除堆顶元素，还有剩余的元素，要进行堆的下沉调整
                siftDown(0, que_[size_]);//把末尾元素放到堆顶0号位置进行调整 
            }
        }
    
        bool empty() const {
         return size_ == 0; }//判空 
    
        int top() const//访问堆顶元素 
        {
        
            if (size_ == 0)
                throw "container is empty!";
            return que_[0];
        }
    
        int size() const {
         return size_; }//数组中的元素个数 
    
    private:
        //入堆上浮调整 O(logn)   O(1)
        void siftUp(int i, int val)
        {
        
            while (i > 0)//最多计算到根节点(0号位)
            {
        
                int father = (i - 1) / 2;//计算当前位置的父节点的下标 
                if (comp_(val, que_[father]))//要插入的元素的值大于父节点的值 
                {
        
                    que_[i] = que_[father];//父节点直接覆盖下来 
                    i = father;//i走到父节点的位置 
                }
                else//要插入的元素的值小于父节点的值，满足大根堆性质，退出循环 
                {
        
                    break;
                }
            }
            //把val放到i的位置
            que_[i] = val;
        }
    
        //出堆下沉调整，时间复杂度是O(logn) 空间复杂度是O(1)
        void siftDown(int i, int val)
        {
        
            //i下沉不能超过最后一个有孩子的节点，因为没有孩子的节点，就不用比较了 
            while (i < size_ / 2)//i<=(size_-1-1)/2 i<=(size_-2)/2  i<=size_-1 i<size/2
            {
        
                int child = 2 * i + 1;//第i个节点的左孩子
                if (child + 1 < size_ && comp_(que_[child + 1], que_[child]))//有右孩子而且右孩子值大于左孩子 
                {
        
                    //如果i节点右孩子的值大于左孩子, child记录右孩子的下标
                    child = child + 1;
                }
    
                if (comp_(que_[child], val))//如果值比较大的那个孩子的值大于其父节点值(val值) 
                {
        
                    que_[i] = que_[child];//值比较大的那个孩子的值直接向上覆盖过去其父节点 
                    i = child;//i下沉到值比较大的那个孩子节点上 
                }
                else//如果值比较大的那个孩子的值小于其父节点值(val值)
                {
        
                    break;//已经满足堆的性质，提前结束
                }
            }
            que_[i] = val;
        }
    private:
        int* que_;//指向动态扩容的数组
        int size_;//数组元素的个数
        int cap_;//数组的总空间大小
        Comp comp_;//比较器对象
    };
    
    int main()
    {
        
        PriorityQueue que;//基于大根堆实现的优先级队列
    
        //基于小根堆实现的优先级队列
        //PriorityQueue que([](int a, int b) {return a < b; });
        srand(time(NULL));
    
        for (int i = 0; i < 10; i++)
        {
        
            que.push(rand() % 100);
        }
    
        while (!que.empty())
        {
        
            cout << que.top() << " ";
            que.pop();
        }
        cout << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3d96004b523249a98ee531e0bdf1b29a.png