优先队列类模版实现：
BuildMaxHeap.h头文件：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include<iostream>
using namespace std;
#define Left(i) i*2+1
#define Right(i) i*2+2
#define Parent(i) (i-1)/2
void Max_Heapify(int a[],int length,int i)
{
int left,right;
left=Left(i);
right=Right(i);
int num=i;
if(left<length&&a[left]>a[i])
{
num=left;
}
//此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确
if(right<length&&a[right]>a[num])
{
num=right;
}
if(num!=i)
{
int temp;
temp=a[i];
a[i]=a[num];
a[num]=temp;
Max_Heapify(a,length,num);
}
}
//此处添加利用循环方式代替递归Max_Heapify的函数，该函数可以替代Max_Heapify
//在某些情况下能取得更好 的效果
void Max_Heapify1(int a[],int length,int i)
{
int left,right,num=i,largest=i;
left=Left(i);
right=Right(i);
while(1)
{
if(a[left]>a[num]&&left<length)
{
largest=left;
}
//此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确
if(a[right]>a[largest]&&right<length)
{
largest=right;
}
if(num!=largest)
{
int temp;
temp=a[num];
a[num]=a[largest];
a[largest]=temp;
num=largest;
left=Left(num);
right=Right(num);
}
else
{
break;
}
}
}
void Build_Max_Heap(int a[],int length )
{
int i;
for(i=(length-1)/2;i>=0;i--)
{
Max_Heapify1(a,length,i);
}
}
void Heap_Sort(int a[],int length)
{
Build_Max_Heap(a,length);
int i;
int temp;
for(i=length-1;i>=1;i--)
{
temp=a[i];
a[i]=a[0];
a[0]=temp;
length-=1;
Max_Heapify1(a,length,0);
}
}
|
PriorQUeue.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include<iostream>
#include "BuileMaxHeap.h"
using namespace std;
#define MAX 100
template <typename type>class PriorQueue
{
private:
int length;
type a[MAX];
public:
PriorQueue ()
{
int i;
length=0;
for(i=0;i<MAX;i++)
{
a[i]=0;
}
}
~PriorQueue()
{
}
void BuildMaxHeapQueue();
void Init(type b[],int len);
type Maxnum();
bool DeleteMax();
void IncreaseKey(int i,type key);
void Insert(type key);
void Print();
void Sort();
};
template<typename type>void PriorQueue<type>::Init(type b[],int len)
{
int i;
this->length=len;
if(len<=0)
{
cout<<"Init failed !"<<endl;
}
for(i=0;i<len;i++)
{
a[i]=b[i];
}
BuildMaxHeapQueue();
}
template<typename type>void PriorQueue<type>::BuildMaxHeapQueue()
{
Build_Max_Heap(a,length);
}
template<typename type>type PriorQueue<type>::Maxnum()
{
if(length<=0)
{
cout<<"the queue is empty!"<<endl;
return -1;
}
return a[0];
}
template<typename type>bool PriorQueue<type>::DeleteMax()
{
if(length<=0)
{
cout<<"the queue is empty!"<<endl;
return 0;
}
a[0]=a[length-1];
length-=1;
Max_Heapify1(a,length,0);
return 1;
}
template<typename type>void PriorQueue<type>::IncreaseKey(int i,type key)
{
int num=i;
if(key<a[num])
{
cout<<"key is error!"<<endl;
return ;
}
a[num]=key;
while(num>0&&a[Parent(num)]<a[num])
{
type temp;
temp=a[num];
a[num]=a[Parent(num)];
a[Parent(num)]=temp;
num=Parent(num);
}
}
template<typename type>void PriorQueue<type>::Insert(type key)
{
if(length>=MAX)
{
cout<<"the queue is full can't add more!"<<endl;
return ;
}
length+=1;
a[length-1]=key;
IncreaseKey(length-1,key);
}
template<typename type>void PriorQueue<type>::Print()
{
int i;
for(i=0;i<length;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
template<typename type>void PriorQueue<type>::Sort()
{
Heap_Sort(a,length);
}
|
main.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include"PriorQueue.h"
#include<iostream>
using namespace std;
int main()
{
PriorQueue<int> node;
int b[10]={4,1,3,2,16,9,10,14,8,7};
node.Init(b,10);
int i;
node.Print();
cout<<endl;
cout<<node.Maxnum()<<endl;
node.DeleteMax();
node.Print();
node.Insert(232);
node.Sort();
node.Print();
return 0;
}
|
以上就是数据结构优先队列的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/liuzhanchen1987/article/details/7705481