今天將繼續加強c++模板類的學習，同時為了鞏固已經學習過的資料結構中有關優先佇列的知識，我將會使用模板類來實現自己的優先佇列。在給出具體實現之前，我要先介紹一下什麼是優先佇列，聊以為複習吧。
在某些情況下，我們會收集一些元素，處理當前元素的最大值，然後再收集更多資料，再處理此時的最大值。這就要求我們設計的資料結構能夠隨時訪問元素集合中的最大值和能夠隨時插入資料。優先佇列即可以實現這種功能。
優先佇列的實現有兩種思路，第一是在資料插入時即儲存資料元素的有序性，這意味著我們能夠以o（1）的時間複雜度來訪問元素中的最大值。但是我們的在資料進行插入的時候，對尋找資料的合適位置的訪問操作的最壞時間複雜度為o(n)。第二種思路是構建一個堆，他能夠然我們以n(1)的時間複雜度來訪問元素中的最大值，而已o(logn)的時間複雜度來調整堆，以便將元素插入到合適的位置。綜上所述，在具體實現優先佇列的時候需要根據待處理的元素量級來確定到底使用哪種思路。很明顯，當數量級較小的時候，適合使用第一種思路；當數量級較大的時候，第二種思路將比較好。
第一種思路由於實現過程不是很複雜，因此我們的重點放在第二中思路上，首先，簡單介紹一下什麼是堆。
1、堆是一種是一種資料結構，他是一顆完全二叉樹。
2、在堆中，每個父節點都大於等於它的兩個孩子節點，被稱為堆有序。
3、如果將堆由上到下，由左到右從0開始編號（即根節點編號為0），則某個節點，它的左孩子編號 = （該節點的編號×2+1）；右孩子節點的編號 = （該節點編號×2+2）。他的第一個存在孩子節點的節點編號為（堆長度/2 - 1）.
在類的定義中，提供了4個建構函式，以及3個具體的資料訪問操作和3個元素佇列狀態的函式。具體如下
classpriority_list;
這只是我們設計的類提供的介面，具體實現如下
#ifndef priority_list_h_included#define priority_list_h_included
#define default_cpty 32template
class
priority_list
//}priority_list(
intval)\
:nofns(
0), capacity(default_cpty), compare(&_compare)
return
; }
priority_list(
bool (*cmp)(t&,t&))\
:nofns(
0), capacity(default_cpty), compare(cmp)
return
; }
priority_list(
int val, bool (*cmp)(t&,t&) )\
:nofns(
0), capacity(default_cpty), compare(cmp)
return
; }
~priority_list()
}bool push(const t& t)//
申請空間成功
obj_cpy(pt, ptt, nofns);//
複製nofns到新的空間中
delete ptt;//
刪除舊的空間
} pt[nofns++] = t;//
加入佇列
heap_up();//
向上重新調整堆。
return
true
; }
bool
pop()
pt[0] = pt[nofns-1];//
將隊尾資料複製到隊頭，
nofns--;//
隊元素個數減一
heap_down(); //
重新向下調整堆
return
true
; }
t top()
return pt[0];//
返回隊頭元素
}
bool is_empty_pl()const
int get_size()const
int get_capacity()const
private
:
void
heap_up();
void
heap_down();
void obj_cpy(t* dest, const t* sour, int n)
bool
static _compare(t &t1, t &t2)
private
: t *pt;//
資料int nofns;//
元素個數
int capacity;//
隊容量bool (*compare)(t&,t&);//
比較函式
};template
void priority_list::heap_up()
break;//
不滿足條件，即已經處在對的位置，直接結束
}
return;}
template
void priority_list::heap_down()
break;//
如果處在對的位置，直接結束，不需要繼續比較下去了
}
return;}
#endif
//priority_list_h_included
在我們的**中存在一些需要改進的地方，在解構函式中，我們並沒有對申請空間失敗進行額外的處理，還有在top函式中，我們對於空佇列的處理存在一些問題。要完美地解決這些問題需要使用到額外的技術--異常處理，但本次實驗的重點不在異常這一塊，因此我們只是簡單地忽略它們。
在本次實驗中，我進一步鞏固了c++中模板c的定義和使用，同時也複習了資料結構中的優先順序佇列相關的知識，尤其是大頂堆和小頂堆這一塊，這對我後面進一步理解堆排序打下了很好的基礎。
C 模板實現優先順序佇列
如果我們給每個元素都分配一個數字來標記其優先順序，不妨設較小的數字具有較高的優先順序，這樣我們就可以在一個集合中訪問優先順序最高的元素並對其進行查詢和刪除操作了。這樣，我們就引入了優先順序佇列 這種資料結構。優先順序佇列 priority queue 是0個或多個元素的集合，每個元素都有一個優先權。...
優先佇列C 陣列實現
優先佇列 include using namespace std class queue node int data int level data data level level node datas 5 int front 隊首 int back 隊尾 int cont 有效個數 public ...
優先佇列學習
priority queue 即在佇列中排隊 1.標頭檔案 include queue using namespace std 2.基本格式 priority queue 結構型別 佇列名 3.priority queue int i 預設的排列為從大到小排列 4.結構體自定義排序方法 在這裡表示一...