数据结构——基于数组的优先级队列模板类实现

逃离我推掉我的手 2022-06-07 09:57 206阅读 0赞

**数据结构笔记3.4**  
与普通的队列不同，优先级队列并不一定按照FIFO（先进先出）的原则对数据进行操纵，而是每次从队列取出具有最高优先权的元素。打个比方，你现在有一堆任务，而你只能一项一项的完成，一种方式是哪项任务先来的你完成哪个；另一种方式是你考虑了各项任务的轻重缓急，然后给他们各自一个优先级序号（就是执行先后次序的序号），你按照这个执行序号来完成每一项任务。这其实就好比是，两种队列的差别。  
优先级队列包括最小优先级队列和最大优先级队列（就是出队元素是按由小到大出，还是由大到小出），这里实现的是最小优先级队列，最大的与之类似。  
而为什么说是基于数组的优先级队列，当然，这是因为还可以利用堆（heap）堆优先级队列进行存储表示，这在后续会有相应的文章。这里给出用数组存储优先级队列的代码，如有不当之处，欢迎各位指正！  
注意的问题：在实现这个类的时候，关键的函数是adjust，他在每次进入队新元素的时候都会调用一次，所以其实每次都是在一个已经有序的数列中插入新的元素（注意区分与数组排序的不同），所以在实现的时候也会有不同。  
算法性能分析：在对数据进行操作的时候涉及到进队函数Insert和出队函数RemoveMin，进队函数的的时间复杂度（为保持数据始终有序，需要用adjust函数对整个数组的元素比较和移动）为：最好的情况进入队列的数据就是整个队中的最大值，这时候不需要移动，最坏的情况是进入的是最小值，这时候需要比较并移动n + 1次（即元素的数量次）。而每次出队一个数据，也需要其后面的所有数据都向前移动进行填补（节约数组空间）。综上，算法的时间复杂度为O(n)。后续我会介绍用heap实现，会将时间复杂度提升到对数级别。下面贴出代码：  
基于数组的优先级队列模板class

//数据结构——基于数组的优先级队列
    #include <iostream>
    #include <cassert>
    using namespace std;
    const int DefaultPQSize = 50;           //优先级队列数组的默认长度
    //优先级队列类定义
    template<class T>
    class PQueue {
    public:
        PQueue(int sz = DefaultPQSize);     //构造函数
        ~PQueue();                         //析构函数
        bool Insert(const T & x);           //将新元素x插入到队尾
        bool RemoveMin(T & x);              //将队头元素删除
        bool GetFront(T & x) const;         //读取队头元素，具有优先权最小的值
        void MakeEmpty();                   //设置优先级队列为NULL
        bool IsEmpty() const;               //判断优先级队列是否为NULL
        bool IsFull() const;                //判断优先级队列是否已FULL
        int GetSize() const;                //求优先级队列中元素的个数
        void Output();                      //队列输出函数
    protected:
        T *pqElements;                      //优先级队列数组
        int count;                          //当前元素的个数（计数器）
        int maxSize;                        //优先级队列最大可容纳元素的个数
        void adjust();                      //队列调整
    };
    //类的函数实现
    template<class T>
    PQueue<T>::PQueue(int sz) {
        //构造函数，建立一个最大具有maxSize元素的NULL的优先级队列
        maxSize = sz;
        count = 0;
        pqElements = new T[maxSize];        //开辟队列空间
        assert(pqElements != NULL);         //断言：检验是否空间分配成功
    }
    
    template<class T>
    PQueue<T>::~PQueue() {
        //析构函数，释放程序所占用的资源
        delete[] pqElements;
    }
    
    template<class T>
    bool PQueue<T>::Insert(const T & x) {
        //若优先级队列不FULL，则将元素插入到队列的队尾,否则返回false
        if (count == maxSize) {             //队列已满返回false
            return false;
        }
        pqElements[count] = x;              //队列不满，将x插入到队尾
        count++;
        adjust();                           //对队列进行权值调整
        return true;                        
    }
    
    template<class T>
    void PQueue<T>::adjust() {
        //将队列元素按其优先级大小调整，保持所有元素按照从小到大有序
        //始终向一个有序数列中插入元素,注意这里并不是对整个数组排序
        T temp = pqElements[count - 1];     //新插入的元素赋值给temp
        for (int j = count - 2; j >= 0; j --) {
            if (pqElements[j] <= temp) {
                break;                      //因为原来的序列已经是有序的，所以只与最后一个元素比较即可
            }
            else {
                pqElements[j + 1] = pqElements[j];
                pqElements[j] = temp;       //插入到合适的位置,并继续循环
            }
        }
    }
    
    template<class T>
    bool PQueue<T>::RemoveMin(T & x) {
        //若队列不为NULL则函数返回具有最大优先权（即最小值）的值，
        //并且删除该元素
        if (0 == count) {                   //优先级队列为NULL，返回错误
            return false;
        }
        x = pqElements[0];
        //运用元素覆盖的方式删除第一个元素（注意下标为0）
        for (int i = 0; i < count - 1; i ++) {
            pqElements[i] = pqElements[i + 1];
        }
        count--;                            //队列元素总数目减1
        return true;
    }
    
    template<class T>
    bool PQueue<T>::GetFront(T & x) const {
        //若优先级队列不为NULL，则返回最大优先级的元素
        if (0 == count) {
            return false;
        }
        x = pqElements[0];
        return true;
    }
    
    template<class T>
    bool PQueue<T>::IsEmpty() const{
        if (0 == count) {
            return true;
        }
        else {
            return false;
        }
    }
    
    template<class T>
    bool PQueue<T>::IsFull() const {
        if (count == maxSize) {
            return true;
        }
        else {
            return false;
        }
    }
    
    template<class T>
    void PQueue<T>::MakeEmpty() {
        //设置优先级队列为NULL
        count = 0;
    }
    
    template<class T>
    int PQueue<T>::GetSize() const {
        return count;
    }
    
    template<class T>
    void PQueue<T>::Output() {
        //按照优先级输出队列中的所有元素
        for (int i = 0; i < count; i ++) {
            cout << pqElements[i] << ' ';
        }
        cout << endl;
    }

Main函数演示代码：

int main()
    {
        PQueue<int> pqueue;
        pqueue.Insert(5);
        pqueue.Insert(3);
        pqueue.Insert(4);
        pqueue.Insert(2);
        pqueue.Insert(7);
        pqueue.Output();        //此时可以看到队列已经有序
        int min_1, min_2;
        pqueue.RemoveMin(min_1);
        pqueue.RemoveMin(min_2);
        pqueue.Output();        //此时可以看到出队的并非最先插入的元素，而是具有最高优先级的元素
    
        system("pause");
        return 0;
    }

运行效果图：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/893e1d1ff1684b6cbe576e0451ab2f1a.png