数据结构（8）优先级队列

队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。

优先级队列有很多实现方案，最常用的是堆，分为大顶堆/小顶堆（大根堆/小根堆），简单来说就是节点的值大于/小于子节点的值。

特别注意堆必须是完全二叉树。

因为完全二叉树的特殊性质，我们可以用数组来存储堆，以此为基础来写大顶堆的class。

首先在头文件里定义maxHeap类，注意数组从【1】开始存储，【0】空着，因为这样左子节点与父节点在序号上刚好就是两倍关系

template<class T>
class maxHeap
{
public:
    maxHeap(int initialCapacity = 10);//构造函数，默认元素个数为10
    ~maxHeap() { delete[] heap; }//析构函数，把存储元素的数组删除
    bool empty() const { return heapSize == 0; }//判断是否为空
    int size() const//返回元素个数
    {
        return heapSize;
    }
    const T& top()//返回最大的元素（第一个元素）
    {// return max element
        if (heapSize == 0)
            throw queueEmpty();
        return heap[1];//数组首元素为空
    }
    void pop();//删除最大元素
    void push(const T&);//插入元素
    void initialize(T*, int);//初始化（接受一个数组，并将其初始化为大顶堆）
    void deactivateArray()//重置
    {
        heap = NULL; arrayLength = heapSize = 0;
    }
    void output(ostream& out) const;//输出
private:
    int heapSize;       // 元素个数
    int arrayLength;    // 长度（容量+1）
    T* heap;            // 存储元素的数组
};

/*-----------------构造函数------------------*/
template<class T>
maxHeap<T>::maxHeap(int initialCapacity)
{// Constructor.
    if (initialCapacity < 1)
    {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
        throw illegalParameterValue(s.str());
    }
    arrayLength = initialCapacity + 1;
    heap = new T[arrayLength];
    heapSize = 0;
}

下面来具体实现各个功能，包括插入，删除，初始化。

个人理解：堆的操作就是基于完全二叉树为基础的，不管插入还是删除都要保重树始终满足完全二叉树的条件

插入操作相对简单，就是从最后一个节点后面新建一个节点，然后和父节点比较是否需要交换，交换后再次判断直到小于父节点或者到顶为止。

template<class T>
void maxHeap<T>::push(const T& theElement)//插入元素
{

   // 首先判断数组长度是否足够
    if (heapSize == arrayLength - 1)
    {
        changeLength1D(heap, arrayLength, 2 * arrayLength);//该函数见《线性表-数组实现》
        arrayLength *= 2;
    }

    //查找应该插入的位置
    int currentNode = ++heapSize;//先给元素个数+1，然后从最后一位开始查
    while (currentNode != 1 && heap[currentNode / 2] < theElement)//如果没到顶且比父节点的元素大
    {
        heap[currentNode] = heap[currentNode / 2]; // 把父节点的元素移下来
        currentNode /= 2;                          //当前元素序号移到父节点
    }

    heap[currentNode] = theElement;
}

删除操作复杂一点。删除操作就是删除首个元素，即最大的元素。

具体步骤为：

1.删除首节点的值

2.提取最后一个元素的值再删除最后的节点，元素个数-1

3.从根节点开始，选出较大的子节点，将值赋予父节点（父节点现在没有值），将最后一个元素的值与当前节点（选出的较大子节点）的较大子节点比较大小，如果最后一个元素大就直接填在这个节点上，如果子节点大就重复操作再向下一层比较，直到比子节点大或者到达最后一层。

template<class T>
void maxHeap<T>::pop()//删除元素
{
   //检查数组是否为空
    if (heapSize == 0)
        throw queueEmpty();

    //把首元素析构
    heap[1].~T();

    // 取出最后一个元素并使元素个数-1
    T lastElement = heap[heapSize--];

    // 
    int currentNode = 1,//当前父节点
        child = 2;     // 当前子节点（默认左节点）
    while (child <= heapSize)//如果子节点序号大于元素个数，说明到底了，退出
    {
        // 判断左右节点哪个大
        if (child < heapSize && heap[child] < heap[child + 1])
            child++;//如果右子节点大就切换到右子节点

        // 最后一个元素是否比当前子节点大
        if (lastElement >= heap[child])
            break;   //比当前子节点大就直接退出循环

        heap[currentNode] = heap[child]; // 交换父子节点
        currentNode = child;             // 当前父节点序号切换到子节点
        child *= 2;                      // 子节点序号切换到左子节点
    }
    heap[currentNode] = lastElement;
}

最后是初始化函数，读取一个数组，并将其转化成大顶堆条件的数组

原理也不复杂，从最后一个有子节点（heapsize/2取整）的节点开始检查是否比子节点大，然后依次检查前一个节点，直到根节点

template<class T>
void maxHeap<T>::initialize(T* theHeap, int theSize)//初始化
{// 读取数组theHeap[1:theSize]并按照大顶堆的要求进行排序
    delete[] heap;//删除原存储数组
    heap = theHeap;//复制输入数组至堆的存储数组
    heapSize = theSize;

    // 从最后一个有孩子的节点开始检查
    for (int root = heapSize / 2; root >= 1; root--)
    {
        T rootElement = heap[root];

        // 孩子的序号是节点的两倍
        int child = 2 * root; 
        while (child <= heapSize)//是否存在字节点
        {
            // 如果有右子节点，那么比较大小判断谁大
            if (child < heapSize && heap[child] < heap[child + 1])
                child++;

            // 是否比较大的孩子节点大
            if (rootElement >= heap[child])
                break;  //是就退出，不需要操作

             // 不是就交换
            heap[child / 2] = heap[child]; 
            child *= 2;                    
        }
        heap[child / 2] = rootElement;
    }
}

大顶堆结构简单，效率很高，属于隐式数据结构，但是当面对合并操作时显得就不是很方便，当对象经常需要合并操作时可以使用左高树这种结构。

首先定义外部节点，即在现有的二叉树所有空位上挂一层外部节点。

s(x)是一个函数，代表了内部节点x到其子树外部节点的最短路径。

如果x是外部节点，那么s(x）= 0。

如果x是内部节点 ,那么s(x) >= 1.

如果x的一个孩子s(x1) = 1,另一个孩子s(x2) = 2,那么s(x) = 2

可以通过递归写出s（x）的解法

s(x)=min(s(L)+s(R))+1

一颗二叉树称为高度优先左高树（height-biased leftist tree,HBLT）。当且仅当其任何一个内部节点的左孩子的s(x) 值都大于或等于右孩子的s值。

左高数的主要操作就是合并，就是一个递归的操作，具体不写了，参见https://blog.csdn.net/qq_41882686/article/details/107423918

当大顶堆实现后，堆排序就很简单了，初始化后一个一个输出顶元素就行了。