目录
  1. 1. 堆 Heap
    1. 1.1. Talk is Cheap, Show me the Code
堆 Heap

堆 Heap

本着能摸鱼就摸鱼的良好习惯,照着C++的STL抄了一套差不(很)多的堆操作…

堆是一棵树,其每个节点都有一个键值,且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆,否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

(小根)堆主要支持的操作有:插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

一些功能强大的堆(可并堆)还能(高效地)支持 merge 等操作。

一些功能更强大的堆还支持可持久化,也就是对任意历史版本进行查询或者操作,产生新的版本。

​ – 来自 OI WIKI

Talk is Cheap, Show me the Code

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
//
// Created by Twiliness on 2019/9/29.
//

namespace Heapify {

struct IterLessIterComparator {
template <typename Iterator1,
typename Iterator2>
constexpr bool operator()(Iterator1 iterator1,Iterator2 iterator2){
return *iterator1 < *iterator2;
}
};

struct IterLessValueComparator {
constexpr IterLessValueComparator() = default;

explicit IterLessValueComparator(IterLessIterComparator) {}

template <typename Iterator,typename Value>
bool operator()(Iterator iterator,Value& value) const {
return *iterator < value;
}
};

template <typename Compare> struct IterValueComparator {
Compare compare;

explicit IterValueComparator(Compare compare) : compare(std::move(compare)) {}

explicit IterValueComparator(const IterValueComparator<Compare> &rhs) : compare(rhs.compare) {}

explicit IterValueComparator(IterValueComparator<Compare> &&rhs)
: compare(std::move(rhs.compare)) {}

template <typename Iterator, typename Value>
constexpr bool operator()(Iterator iterator, Value value) {
return bool(compare(*iterator, value));
}
};

template <typename Compare>
struct IterIterComparator {
Compare compare;

explicit constexpr IterIterComparator(Compare compare) : compare(std::move(compare)) {}

template <typename Iterator1,typename Iterator2>
bool operator()(Iterator1 iterator1,Iterator2 iterator2){
return bool(compare(*iterator1,*iterator2));
}
};

template <typename Compare>
constexpr inline IterIterComparator<Compare> generateIterIterComparator(Compare compare){
return IterIterComparator<Compare>(std::move(compare));
}

constexpr inline IterLessIterComparator generateIterLessIterComparator(){
return IterLessIterComparator();
}

inline IterLessValueComparator generateIterLessValueComparator() {
return IterLessValueComparator();
}

template <typename Compare>
inline IterValueComparator<Compare> generateComparator(Compare compare) {
return IterValueComparator<Compare>(std::move(compare));
}

template <typename Compare>
inline IterValueComparator<Compare> generateComparator(IterValueComparator<Compare> compare) {
return IterValueComparator<Compare>(std::move(compare));
}



template <typename Iterator,
typename Distance,
typename Type,
typename Compare>
void push_heap(Iterator begin,Distance hole,Distance top,Type value,Compare& compare){
Distance parent = (hole - 1) / 2;

while(hole > top && compare(begin + parent,value)){
*(begin + hole) = std::move(*(begin + parent));
hole = parent;
parent = (hole - 1) / 2;
}

*(begin + hole) = std::move(value);
}

template <typename Iterator, typename Compare>
inline void push_heap(Iterator begin, Iterator end, Compare compare) {
typedef typename std::iterator_traits<Iterator>::value_type valueType;
typedef typename std::iterator_traits<Iterator>::difference_type distanceType;

decltype(generateComparator(std::move(compare))) comparator(
std::move(compare));

valueType value = std::move(*(end - 1));

push_heap(begin, distanceType (end - begin - 1), distanceType (0), std::move(value), comparator);
}

template <typename Iterator>
inline void push_heap(Iterator begin,Iterator end){
typedef typename std::iterator_traits<Iterator>::value_type valueType;
typedef typename std::iterator_traits<Iterator>::difference_type distanceType;

IterLessValueComparator comparator;

valueType value = std::move(*(end - 1));
push_heap(begin,distanceType(end - begin - 1),distanceType(0),std::move(value),comparator);
}

template <typename Iterator, typename DistanceType, typename Type,
typename Compare>
void adjust_heap(Iterator begin, DistanceType hole, DistanceType length,
Type value, Compare compare) {
const DistanceType topIdx = hole;

DistanceType child = hole;

while (child < (length - 1) / 2) {
child = 2 * (child + 1);

if (compare(begin + child, begin + child - 1))
--child;

*(begin + hole) = std::move(*(begin + child));
}

if ((length & 1) == 0 && child == (length - 2) / 2) {
child = 2 * (child + 1);

*(begin + hole) = std::move(*(begin + child - 1));

hole = child - 1;
}

decltype(generateComparator(std::move(compare))) comparator(
std::move(compare));

push_heap(begin, hole, topIdx, std::move(value), comparator);
}

template <typename Iterator, typename Compare>
void make_heap(Iterator begin, Iterator end, Compare &comp) {
typedef typename std::iterator_traits<Iterator>::value_type valueType;
typedef typename std::iterator_traits<Iterator>::difference_type distanceType;

if (end - begin < 2)
return;

const distanceType length = end - begin;

distanceType parent = (length - 2) / 2;

while (true) {
valueType value = std::move(*(begin + parent));

adjust_heap(begin, parent, length, std::move(value), comp);

if (parent == 0)
return;

--parent;
}
}

template <typename Iterator>
inline void make_heap(Iterator begin,Iterator end){
IterLessIterComparator comparator;

make_heap(begin,end,comparator);
}

template<typename Iterator, typename Compare>
void pop_heap(Iterator begin,Iterator end,Iterator result,Compare& compare){
typedef typename std::iterator_traits<Iterator>::value_type valueType;
typedef typename std::iterator_traits<Iterator>::difference_type distanceType;

valueType value = std::move(*result);
*result = std::move(*begin);

adjust_heap(begin,distanceType(0),distanceType(end - begin),std::move(value),compare);
}

template <typename Iterator>
inline void pop_heap(Iterator begin,Iterator end){
if (end - begin > 1)
{
--end;
IterLessIterComparator __comp;
pop_heap(begin, end, end, __comp);
}
}

template <typename Iterator,typename Compare>
inline void pop_heap(Iterator begin,Iterator end,Compare compare){
if (end - begin > 1){
typedef decltype(compare) Comparator;

IterIterComparator<Comparator> comparator(std::move(compare));

--end;
std::pop_heap(begin,end,end,comparator);
}
}

template <typename Iterator,typename Compare>
void sort_heap(Iterator begin,Iterator end,Compare& compare){
while(end - begin > 1) {
--end;
pop_heap(begin,end,end,compare);
}
}

template <typename Iterator>
inline void sort_heap(Iterator begin,Iterator end){
IterLessIterComparator comparator;

sort_heap(begin,end,comparator);
}

template <typename Iterator,typename Compare>
inline void sort_heap(Iterator begin,Iterator end,Compare compare){
typedef decltype(compare) CompareType;

IterIterComparator<CompareType> comparator(std::move(comparator));
sort_heap(begin,end,comparator);
}

}
文章作者: Twiliness
文章链接: https://twiliness.xyz/2019/09/30/Heap/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Twilight Spring