堆得應用【一】--【優先級隊列priority_queue】

先看一下STL中優先級隊列實作的功能：

一、介紹優先級隊列

優先級隊列就是每次top可以取到隊列的最值；每次pop都能删除隊列中的最值；

那麼我們應該如何實作呢？

優先級隊列是我們常見的資料結構隊列的一種變形，對于隊列，大家都很熟悉；就是先進如隊列的元素，先出隊列，那麼一般的隊列是可以尾插，可以頭删，可以取到頭部的元素,，可以到尾部取元素；我們要将一般隊列實作優先級隊列有三種方法：

方法一：就是我們在插入資料【push】時候，每次從集合中找到一個最值，尾插到隊列中，這樣經過n次那麼集合中的m個資料就會按照順序裝入隊列中,是以插入的時間複雜度【O(N^2)】，那麼這種情況，我們取隊列的最值，隻要取頭部【Top】的元素，就可以取到，時間複雜度【O(1)】；我們删除【Pop】隊列的最值，也隻要删除頭部元素即可，時間複雜度【O(1)】;

方法二：我們可以每次将幾個中的元素按照集合的順序依次插入【Push】隊列中，那麼時間複雜度為O(N);這時在取隊列的最值【Top】時，我們就要每次将隊列的元素周遊一遍才能找到最值删除隊列【Pop】的最值，也是将隊列的元素找一遍，找到最值才能删除而且這樣由于隊列隻能檢視頭部元素和尾部元素，那麼在尋找最值的時候，還要pop掉頭部元素，才能檢視下一個元素，；而且在找完之後還要在将删除的元素裝入隊列，是以時間複雜度更高，是以這種方法太挫；不選；

方法三：就是我們不用隊列的資料結構實作優先級隊列；

我們用堆得資料【Heap】結構實作優先級隊列；

【Push】時，直接将資料push進堆裡；時間複雜度O（logN);

【Top】時，直接從堆中拿最頂端的元素（即數組下标為0的元素），時間複雜度O(1);

【Pop】時，直接從堆中删除最值元素，即數組的第一個元素，時間複雜度O(logN);

二、代碼實作:

#include<iostream>
using namespace std;
#include"Heap.h"

template<typename T,typename Compare>
class PriorityQueue
{
public:
    PriorityQueue(const T* arr,int sz)
        :_heap(arr,sz)
    {}
    void Push(const T& x)//向優先級隊列中添加元素
    {
       _heap.Push(x);
    }
    void Pop()//删除優先級最高的元素--即最大元素或者最小元素
    {
       _heap.Pop();//删除堆得0小标元素，然後向下調整堆
    }
    const T& Top()//傳回優先級隊列最高的元素--即最大元素或者最小元素
    {
       return _heap.Top();//傳回堆得第一個元素
    }
    size_t Szie()//傳回優先級隊列的元素個數
    {
       return _heap.Size();//傳回堆得元素個數
    }
    bool Empty()//判斷優先級隊列是否為空
    {
       return _heap.Empty();
    }
private:
    Heap<T,Compare> _heap;
};

int main()
{
      int a [] = {,, , , , , , , , };
      int sz=sizeof(a)/sizeof(a[]);
      PriorityQueue<int,Small<int>> pq(a,sz);
      cout<<pq.Top()<<endl;
      cout<<pq.Szie()<<endl;
      cout<<pq.Empty()<<endl;


      pq.Push();
      cout<<pq.Top()<<endl;
      cout<<pq.Szie()<<endl;
      cout<<pq.Empty()<<endl;

      pq.Pop();
      cout<<pq.Top()<<endl;
      cout<<pq.Szie()<<endl;
      cout<<pq.Empty()<<endl;
}