优先队列学习总结

川长思鸟来 2022-03-01 11:41 194阅读 0赞

普通的队列，遵循先进先出的规则，进行元素的添加和查询，但是对于很多情况下，我们想要在序列中找符合我们要求的元素(`比如序列中最大的元素`)，这时候，无论是普通的线性表还是线性表中比较特殊的栈或者队列，找到该指定元素的范围都会卡在时间复杂度为O(n)的级别，其实我们完全可以实现查找时间复杂度降为O(1)，就是通过优先队列来实现！

--------------------

我们需要做的就是，给元素赋予一种`优先级`（比如说：要是我们在使用中总想拿出队列中最大的元素），我们创建队列时，就将优先级最高的元素放在队首，最后想要的时候就可以直接拿走队首元素了。也就是说整个优先队列是按照优先级从高到低创建出来的。

所以说，怎们实现这种设想呢？  
实现以上想法，我们需要创建一个最大堆(`因为建最小堆是同样的道理，所以之一最大堆为例来说明`)，如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]不难看出，最大堆对应的就是最大优先队列，通过完全二叉树实现，选择[完全二叉树][Link 1]的理由：  
易于操作，如果创建一个数组存这个完全二叉树，以根节点开始下标为0，下面的子孙从左往右下标为1，2，3…可以发现：

左孩子节点下标 = 2×对应根节点下标+1 
    右孩子节点下标 = 2×对应根节点下标+2
    
    父亲节点下标 = (孩子节点-1)/2

我们在往数组中录入数据时，将数据先添加到数组最后一个位置，然后根据以上公式将该叶子节点和其父亲节点大小进行比较，如果比父亲节点大的话，将父亲节点移下来，用子节点提还，直到找到比当前新添加元素大的父亲节点为止，以后添加节点都这样整就行。这样就使整个数组将数据存为最大优先队列的形式。

PS.`这样只保证了根为整个队列的最大元素，并不能保证离根远的叶子节点一定小于其他离根近叶子节点`

要是出队的话，将最大元素返回，然后要删除队列中的最大元素，这时就需要重新调整堆的结构了，怎样调呢？  
将数组中最后一个元素的调到根，并删掉其对应的最后一个位置，从根节点开始开始`下沉`，即就是

>  *  根节点的数据与叶子节点相比较，要是比叶子节点都小的话，和最大的叶子节点进行数据交换；
>  *  要是某个子节点比根节点大的话，就和相应的子节点进行交换即可。
>  *  不断下沉…知道满足根节点比其任意子节点大即可。

综上，往堆中添加元素的时间复杂度为O(log(n))，从队列中删除元素的时间复杂度为O(log(n))，都比遍历整个序列O(n)这个时间复杂度要小。

--------------------

#include <iostream>
    #include<vector>
    #include<iterator>
    using namespace std ;
    #define MAX 65535
    //最大堆实现
    //保证子节点不大于其对应的父节点的值
    //设置元素个数接口
    //是否为空的接口
    //获取父亲节点的接口
    
    class Dui
    {
        
    
    private :
    
        vector<int>p ;
        int last ;
    
    public :
        Dui()
        {
        
        }
        ~Dui(){
        }
    
    public :
    
        void print()
        {
        
            int i ;
            while(1)
            {
        
                cin >> i ;
                if(i == -1)
                {
        
                    break ;
                }
                add(i) ;
            }
    
            cout << "这是一个最大堆" << endl ;
            for(int i=0 ; i <= last; i++)
            {
        
    
                cout << p[i] <<endl ;
            
            }
    
            cout << "当前最大堆顶部元素是" << endl ;
            cout << getMax() << endl ;
            cout << "堆尾元素" << endl ;
            cout << p[last] <<endl ;
        }
        //往堆中添加元素
        void add(int e)
        {
        
            p.push_back(e) ;
            last = p.size() - 1 ;
            siftUp();
        }
        
        //交换父子节点信息
        void swap( int& t1, int& t2 )
        {
           
            int s ;
            s = t1 ;
            t1 = t2 ;
            t2 = s ;
        }
        
        //获取堆的规模
        int get_size()
        {
        
            return last+1 ;
        }
    
        //获取其父亲节点的下表
        int getParent(int index)
        {
        
            return (index-1)/2 ;
        }
    
        //将添加的元素移动到正确的位置
        void siftUp()
        {
        
            //堆中的子节点不能大于其父结点的值
            int f = getParent(last) ;          
            int cur = last ;
    
            while(cur >0 && p[f] < p[cur])
            {
        
                swap(p[f], p[cur]) ;
                cur = getParent(cur);
                f = getParent(cur) ;
            }
        }
        
        //获取其左孩子的下标
        int get_right_child(int index)
        {
        
            return index*2+2 ;
        }
    
        //获取其右孩子的下标
        int get_left_child(int index)
        {
        
            return index*2+1 ;
        }
    
        //从堆顶开始比较父亲节点和字节点的大小
        //要是父亲节点比其子节点要小的话，交换两者的值
        void change(int& left, int& right, int& cur, int& swaps)
        {
        
              swap(p[swaps], p[cur]) ;
              cur = swaps ;
              left = get_left_child(swaps) ;  
              right = get_right_child(swaps) ;
        }
    
        //从堆顶调整使整个堆保持为完全二叉树
        void siftDown()
        {
        
            int cur = 0 ;
            int left = get_left_child(0) ;
            int right = get_right_child(0) ;
    
            while(left < last&&(p[cur] < p[left]||p[cur] < p[right]))
            {
        
                
                if(left == last && right >last )
                {
        
                      if(p[right] > p[cur])  
                      {
        
                          swap(p[right], p[cur]) ;
                          break ;
                      }
                } 
                //如果左右节点都比其父亲节点大,找最大的那个进行交换
                else if(p[cur] < p[left] && p[cur] < p[right])
                {
        
                    if(p[left] < p[right])
                    {
        
                        change(left, right, cur, right) ;
                    }
    
                    else
                    {
        
                        change(left, right, cur, left) ;
                    }
                }
                else
                {
        
                    if(p[left] > p[cur])
                    {
        
                        change(left, right, cur, left) ;
                    }
                    else
                    {
        
                        change(left, right, cur, left) ;
                    }
                }
            }
        }
    
        //从堆中取出最大元素
        int getMax()
        {
        
            //获取到最大元素
            int max_ = p[0] ;
            cout << max_ <<endl ;
            int ll = p[last] ;
            //将最后一个元素获取到
            p[0] = ll ;
            siftDown() ;
            remove_last() ;
            return max_ ;
        }
    
        //将最后一个元素删除掉
        void remove_last()
        {
        
            p.pop_back() ;
            last -- ;
        }
    };
    ///test 例子
    int main()
    {
        
        Dui dd ;
        dd.print() ; 
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190322141734458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[Link 1]: /images/20220301/095df2f75321484bbff9a7c1824890cd.png