手把手教你實現一個優先隊列

05-06

1、優先隊列簡介

優先隊列首先是隊列，但相對於隊列的先進先出而言，它的特性在於高效地將隊列中優先順序最高的那個元素彈出來（複雜度O(lgN)）。這個特性十分有用，最直接的一個用途就是排序，採用選擇排序的思想，利用優先隊列，就能把演算法複雜度從O(N^2)優化成O(NlgN)。

2、優先隊列的實現

首先，作為一個優先隊列，需要有以下三個基本成員：

private: int sz;//優先隊列大小 int capacity;//優先隊列容量 int*pq;//數組，保存優先隊列里的元素

然後是基本的構造函數和析構函數：

public: PQ(int n){//構造函數 pq=new int[n+1];//pq[0]不使用 sz=0; capacity=n; } ~PQ(){//析構函數 delete []pq; }

重點來了，雖然優先隊列使用數組保存，但其邏輯上的結構是二叉樹：

作為優先隊列，最重要的兩個操作分別是插入和刪除，搞懂這兩個就搞懂了優先隊列

簡單介紹一下這兩個操作的流程：

1）插入

a、如果隊列大小已達到上限，則將隊列容量翻倍。否則進行步驟b。

b、隊列大小加一，將新元素插入到數組最後的位置。

c、將新元素和其邏輯上的父親節點進行優先順序比較，如果新元素的優先順序比父親節點高，則交換兩者的位置。一直比較下去（最多lgN次比較），直到父節點比新元素優先順序高或者已經到達二叉樹的頂端。（即上浮操作）

void swim(int n){ while(n>1&&cmp(pq[n],pq[n>>1])){//如果pq[n]比父節點的優先順序大，將其上浮 swap(pq[n],pq[n>>1]); n>>=1; } }

void insert(int val){ if(sz>=capacity){//如果存儲範圍超過了capacity，則將容量擴展為二倍 int* temp=new int[capacity<<1]; for(int i=1;i<=capacity;i++){ temp[i]=pq[i]; } delete []pq; pq=temp; capacity<<=1; } sz++; pq[sz]=val; swim(sz);//將新插入的元素進行上浮操作 }

2）刪除

a、將優先順序最高（即數組第一個元素）與數組最後一個元素進行交換。數組大小減一。

b、將放在第一個的元素和左右孩子中較大的那一個進行比較，如果優先順序低於孩子，則交換二者的位置。一直進行此操作直到抵達數組末尾或者優先順序不低於孩子為止。（即下沉操作）

void sink(int n){ while(2*n<=sz){ int k=2*n; if(k<sz&&cmp(pq[k+1],pq[k]))k++;//選出左右孩子中優先順序更高的那個 if(cmp(pq[k],pq[n])){//如果pq[n]的優先順序低，將其下沉 swap(pq[n],pq[k]); n=k; }else break; } }

int pop(){//彈出優先度最高的元素 int temp=pq[1]; swap(pq[1],pq[sz--]); sink(1); return temp; }

其他的操作就很簡單了，放代碼在下面，注釋很詳細，供參考：

三、完整優先隊列類代碼

class PQ{private: int sz;//優先隊列大小 int capacity;//優先隊列容量 int*pq;//數組保存優先隊列里的元素public: PQ(int n){//構造函數 pq=new int[n+1];//pq[0]不使用 sz=0; capacity=n; } ~PQ(){//析構函數 delete []pq; } void insert(int val){ if(sz>=capacity){//如果存儲範圍超過了capacity，則將容量擴展為二倍 int* temp=new int[capacity<<1]; for(int i=1;i<=capacity;i++){ temp[i]=pq[i]; } delete []pq; pq=temp; capacity<<=1; } sz++; pq[sz]=val; swim(sz);//將新插入的元素進行上浮操作 } int top(){//返回優先度最高的元素 return pq[1]; } int pop(){//彈出優先度最高的元素 int temp=pq[1]; swap(pq[1],pq[sz--]); sink(1); return temp; } int size(){ return sz; } bool empty(){ return sz==0; }private: bool cmp(int a,int b){ return a<b; } void swim(int n){ while(n>1&&cmp(pq[n],pq[n>>1])){//如果pq[n]比父節點的優先順序大，將其上浮 swap(pq[n],pq[n>>1]); n>>=1; } } void sink(int n){ while(2*n<=sz){ int k=2*n; if(k<sz&&cmp(pq[k+1],pq[k]))k++;//選出左右孩子中優先順序更高的那個 if(cmp(pq[k],pq[n])){//如果pq[n]的優先順序低，將其下沉 swap(pq[n],pq[k]); n=k; }else break; } }};

3、實戰練習

hihoCoder?

hihocoder.com

#1105 : 題外話·堆
時間限制:10000ms
單點時限:1000ms
內存限制:256MB
描述
小Ho有一個糖果盒子，每過一段時間小Ho都會將新買來的糖果放進去，同時他也會不斷的從其中挑選出最大的糖果出來吃掉，但是尋找最大的糖果不是一件非常簡單的事情，所以小Ho希望能夠用計算機來他幫忙計算這個問題！

提示：吃糖果吃多了會變胖的！輸入
每個測試點（輸入文件）有且僅有一組測試數據。
在一組測試數據中：
第1行為1個整數N，表示需要處理的事件數目。
接下來的M行，每行描述一個事件，且事件類型由該行的第一個字元表示，如果為A，表示小Ho將一粒糖果放進了盒子，且接下來為一個整數W，表示這顆糖果的重量；如果為T，表示小Ho需要知道當前盒子中最重的糖果的重量是多少，在知道這個值之後，小Ho會將這顆糖果從盒子中取出並吃掉。
對於100%的數據，滿足1<=N<=10^5, 1<=w<=10^5。<>
對於100%的數據，滿足沒有2顆糖果的重量是相同的，最開始的時候小Ho的糖果盒子是空的，且每次小Ho想要取出一顆糖果的時候盒子里一定至少有一顆糖果。
輸出
在一組測試數據中：
對於每個類型為T的時間，輸出1個整數W_MAX，表示在這一時刻，盒子中最重的糖果的重量。

樣例輸入5
A 77751
A 1329
A 26239
A 80317
T
樣例輸出
80317

題很簡單，利用優先隊列的特性即可。

#include <iostream>using namespace std;class PQ{private: int sz;//優先隊列大小 int capacity;//優先隊列容量 int*pq;//數組保存優先隊列里的元素public: PQ(int n){//構造函數 pq=new int[n+1];//pq[0]不使用 sz=0; capacity=n; } ~PQ(){//析構函數 delete []pq; } void insert(int val){ if(sz>=capacity){//如果存儲範圍超過了capacity，則將容量擴展為二倍 int* temp=new int[capacity<<1]; for(int i=1;i<=capacity;i++){ temp[i]=pq[i]; } delete []pq; pq=temp; capacity<<=1; } sz++; pq[sz]=val; swim(sz);//將新插入的元素進行上浮操作 } int top(){//返回優先度最高的元素 return pq[1]; } int pop(){//彈出優先度最高的元素 int temp=pq[1]; swap(pq[1],pq[sz--]); sink(1); return temp; } int size(){ return sz; } bool empty(){ return sz==0; }private: bool cmp(int a,int b){ return a>b; } void swim(int n){ while(n>1&&cmp(pq[n],pq[n>>1])){//如果pq[n]比父節點的優先順序大，將其上浮 swap(pq[n],pq[n>>1]); n>>=1; } } void sink(int n){ while(2*n<=sz){ int k=2*n; if(k<sz&&cmp(pq[k+1],pq[k]))k++;//選出左右孩子中優先順序更高的那個 if(cmp(pq[k],pq[n])){//如果pq[n]的優先順序低，將其下沉 swap(pq[n],pq[k]); n=k; }else break; } }};int main(){ int n; cin>>n; PQ q(n); while(n--){ char ch; cin>>ch; if(ch==A){ int temp; cin>>temp; q.insert(temp); } if(ch==T){ cout<<q.pop()<<endl; } } return 0;}

結果：

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

歡迎掃碼關注~