一个简单的Heap实现

一下代码实现了一个堆,可以传入仿函数来决定生成最大堆或最小堆。

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#ifndef _HEAP_
#define _HEAP_
#include"../Vector/Vector.h"
#include<string>
using namespace std;
template<typename T>
class Less{
public:
bool operator()(const T& t1,const T& t2)
{
return t1<t2;
}
};
template<typename T>
class Greater{
public:
bool operator()(const T& t1,const T& t2)
{
return t1>t2;
}
};
template<typename T,typename Compair=Less<T>>
class heap{
public:
heap():_vector()
{}
heap(const MyVector<T>& v):_vector(v)
{
make_heap();
}
~heap()
{}
heap(const heap& h)
{
_vector=h._vector;
}
heap& operator=(const heap& h)
{
_vector=h._vector;
}
const T& top()
{
if(empty())
throw new string("heap is null!");
return _vector[0];
}
void make_heap()
{
int i;
int n=_vector.size();
for(i=n/2;i>=0;--i)
{
_JustDown(i,n);
}
}
void push_heap(const T& t)
{
Compair cp;
_vector.push_back(t);
int i=_vector.size()-1;
for(;i>=0;)
{
if(cp(_vector[i],_vector[i/2]))
{
swap(_vector[i],_vector[i/2]);
i=i/2;
}
else
{
break;
}
}
}
bool empty()
{
return _vector.empty();
}
size_t size()
{
return _vector.size();
}
T pop_heap()
{
if(empty())
throw new string("heap is null!");
swap(_vector[0],_vector[_vector.size()-1]);
T tmp=_vector[_vector.size()-1];
_vector.pop_back();
_JustDown(0,_vector.size());
return tmp;
}
void sort_heap()
{
if(empty())
throw new string("heap is null!");
int i=_vector.size()-1;
for(;i>0;)
{
swap(_vector[0],_vector[i]);
_JustDown(0,i);
i--;
}
}
void Print()
{
int i;
for(i=0;i<_vector.size();++i)
{
cout<<_vector[i]<<" ";
}
cout<<endl;
}
private:
void _JustDown(int s,int n)
{
Compair cp;
if(n<=1)
return;
if(s>=n)
return;
int i;
for(i=s;i<n;)
{
if(i*2+2<n)
{
int select=cp(_vector[i*2+1],_vector[i*2+2])?i*2+1:i*2+2;
select=cp(_vector[select],_vector[i])?select:i;
if(i!=select)
{
swap(_vector[i],_vector[select]);
i=select;
}
else
{
break;
}
}
else if(i*2+1<n)
{
if(cp(_vector[i*2+1],_vector[i]))
swap(_vector[i],_vector[i*2+1]);
i=i*2+1;
}
else
{
break;
}
}
}
private:
MyVector<T> _vector;
};
#endif

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往