優先級隊列——堆

優先級隊列的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;
    }
}