《算法与数据结构---C语言描述》优先队列

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　所谓的优先队列，其实是一个二叉树，只是这个树比较特别，小数据的结点一定在大数据的结点之上，又称“小根堆”。

　　搞了几天，终于把优先队列搞定了，当然，也是这几天老是分神，QQ还是在白天设置成免打扰模式吧。

　　以下是代码

View Code

 1 #ifndef PriorityLEAP_H
 2 #define PriorityLEAP_H
 3 
 4 template<class T>
 5 class PriorityLeap
 6 {
 7 public:
 8     PriorityLeap(T d){
 9         llink = NULL;
10         rlink = NULL;
11         plink = NULL;
12         data = d;
13     }
14 
15     void 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     }
43     T 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     }
72     bool isEmpty()
73     {
74         if(llink==NULL && rlink == NULL){
75             return true;
76         }
77         return false;
78     }
79 public:
80     T data;
81     PriorityLeap* llink;
82     PriorityLeap* rlink;
83     PriorityLeap* plink;
84 };
85 #endif

View Code

 1 int _tmain(int argc, _TCHAR* argv[])
 2 {
 3     char s_a = 'a';
 4     char s_b = 'b';
 5     char s_c = 'c';
 6     char s_d = 'd';
 7     char s_e = 'e';
 8     char s_f = 'f';
 9 
10     PriorityLeap<char> leap(s_f);
11     leap.add_heap(s_d);
12     leap.add_heap(s_e);
13     leap.add_heap(s_c);
14     
15     for (int i = 0; i < 4; i++)
16     {
17         printf("priorityleap %c\n",leap.removeMini_heap());
18     }
19 
20     system("pause");
21     return 0;
22 }