优先级队列——堆

优先级队列的C++队列

堆 是实现优先级队列效率很高的数据结构。堆是一棵完全二叉树，用二叉树的数组表示法最有效率。在链表结构中，在高度和重量上左高树也适合于表示优先级队列。

堆 ：是一棵二叉树，且节点数据有顺序要求。最大堆（大根堆）：每个节点的值都大于等于其子节点的值。最小堆（小根堆）：每个节点的值都小于等于其子节点的值。

优先级队列 是 0 个或多个元素的集合，每个元素都有一个优先权或值，对优先级队列执行的操作有 1）查找一个元素-top；2）插入一个元素-push；3）删除一个元素-pop。

最大（小）优先级队列 ：查找和删除的元素都是优先级做大（小）的元素。对于相同优先级的元素，查找和删除的顺序可以任意处理。

1. 最大优先级队列的抽象数据类型

template<class T>
class maxPriorityQueue
{
    public:
        virtual ~maxPriorityQueue() {}
        virtual bool empty() const = 0;
        virtual int size() const = 0;
        virtual const T& top() = 0;
        virtual void pop() = 0;
        virtual void push(const T& theElement) = 0; 
};
           

1. 最大堆类 maxHeap

   此处堆的底层实现是一维数组，按照完全二叉树的编号，将编号对应于数组下标，下标 0 弃用。即：heap[1] 为根节点，heap[2]、heap[3] 是 heap[1] 的孩子节点，heap[4]、heap[5] 是 heap[2] 的孩子节点，依此类推。

template<class T>
class maxHeap : public maxPriorityQueue<T>
{
    public:
        maxHeap(int initialCapacity = 10);
        ~maxHeap() 
        {
            delete [] heap;
        }

        bool empty() const
        {
            return heapSize == 0;
        }

        int size() const
        {
            return heapSize;
        }

        const T& top()
        {
            if (heapSize == 0)
            {
                throw queueEmpty();
            }

            return heap[1];
        }

        void pop();
        void push();
        void initialize(T*, int);

    private:
        T *heap;
        int heapSize;
        int arrayLength;
};
           

1. 向最大堆添加元素

   将新元素插入到新节点，然后沿着从新节点到根节点的路径，执行一趟“起泡”操作，将新元素与其父节点的元素比较交换，直到后者大于等于前者为止。

   时间复杂度：O(height) = O(logn)

template<class T>
void maxheap<T>::push(const T& theElement)
{
    // 若底层实现的数组容量不够时，对数组进行扩容
    if (heapSize == arrayLength - 1)
    {
        changeLength1D(heap, arrayLength, 2 * arrayLength);
        arrayLength *= 2;
    }

    int currentNode = ++heapSize;

    // 向上起泡
    while (currentNode != 1 && heap[currentNode / 2] < theElement)
    {
        heap[currentNode] = heap[currentNode / 2];
        currentNode /= 2; 
    }

    heap[currentNode] = theElement;
}
           

1. 从最大堆删除最大元素

   删除的是最大的元素，即根元素。删除以后，将堆的最后一个元素保存起来，并调整堆的大小（–heapSize）。从被删除的根节点开始，尝试着将堆尾元素放置于此，若可以放置则结束，若不可以放置，将当前根节点的较大孩子节点放在当前根节点处，再尝试将堆尾元素放置在较大孩子节点处，如此循环至堆尾。

   时间复杂度：O(height) = O(logn)

template<class T>
void maxheap<T>::pop()
{
    if (heapSize == 0)
    {
        throw queueEmpty();
    }

    heap[1].~T();

    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;    
}
           

1. 初始化一个非空最大堆

   最大堆的初始化，可以理解成对 n 个元素进行插入操作。

   基本思路：从最后一个拥有孩子节点的节点（i = n / 2）开始，若以该元素为根的子树不是最大堆，则将这个子树调整为最大堆。然后继续检查以 i - 1 节点为根的子树，直至检查至以 1 为根的树为止。

   时间复杂度：上限 O(nlogn) ，平均 O(n) 。

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;
    }
}