所谓的优先队列，其实是一个二叉树，只是这个树比较特别，小数据的结点一定在大数据的结点之上，又称“小根堆”。
搞了几天，终于把优先队列搞定了，当然，也是这几天老是分神，QQ还是在白天设置成免打扰模式吧。
以下是代码
View Code
1 #ifndef PriorityLEAP_H
2 #define PriorityLEAP_H
3
4 template<class T>
5 class PriorityLeap
6 {
7 public:
8PriorityLeap(T d){
9 llink = NULL;
10 rlink = NULL;
11 plink = NULL;
12 data = d;
13}
14
15void add_heap(T d)
16{
17 //1.移到树叶，
18 //2.向上移，直到要结点或者父结点比插入的节点大
19 PriorityLeap* leaf = this;
20 PriorityLeap* add = new PriorityLeap(data);
21 add->data = d;
22 while (leaf->llink != NULL )
23 {
24 leaf = leaf->llink;
25 }
26 leaf->llink = add;
27 add->plink = leaf;
28 int begin = false;
29 while ( leaf != NULL && d < leaf->data )
30 {
31 leaf->llink->data = leaf->data;
32
33 if(leaf->plink ==NULL){
34 leaf->data = d;
35 begin = true;
36 break;
37 }
38 leaf = leaf->plink;
39 }
40 if(!begin)
41 leaf->llink->data = d;
42}
43T removeMini_heap()
44{
45 T ret = data;
46
47 PriorityLeap* temp = this;
48 PriorityLeap* t = NULL;
49
50 while (temp && (temp->llink != NULL || temp->rlink != NULL) )
51 {
52 t = temp;
53 if ( temp->llink == NULL ){
54 temp = temp->rlink;
55 }
56 else if ( temp->rlink == NULL ){
57 temp = temp->llink;
58 }
59 else if ( temp->llink->data > temp->rlink->data){
60 temp = temp->llink;
61 }
62 else{
63 temp = temp->rlink;
64 }
65
66 t->data = temp->data;
67
68 }
69
70 return ret;
71}
72bool isEmpty()
73{
74 if(llink==NULL && rlink == NULL){
75 return true;
76 }
77 return false;
78}
79 public:
80T data;
81PriorityLeap* llink;
82PriorityLeap* rlink;
83PriorityLeap* plink;
84 };
85 #endif
View Code
1 int _tmain(int argc, _TCHAR* argv[])
2 {
3char s_a = 'a';
4char s_b = 'b';
5char s_c = 'c';
6char s_d = 'd';
7char s_e = 'e';
8char s_f = 'f';
9
10PriorityLeap<char> leap(s_f);
11leap.add_heap(s_d);
12leap.add_heap(s_e);
13leap.add_heap(s_c);
14
15for (int i = 0; i < 4; i++)
16{
17 printf("priorityleap %c\n",leap.removeMini_heap());
18}
19
20system("pause");
21return 0;
22 }
