优先队列学习总结

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