MinMaxHeap，最小最大堆，或称双端优先队列，提供操作
最小最大堆是一棵完全二叉树，且其中每个元素有一个key数据成员。树的各层交替为最小层和最大层。根结点在最小层。设x是最小最大堆的任意结点。若x在最小（最大）层上，则x中的元素的key值在以x为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为最小（最大）结点。
1）插入
和普通的堆一样，先放到堆尾再调整。调整的过程，以插入元素在小根层为例：先和父亲比较，如果大于父亲则和父亲对调，以后在只在大根层作大顶堆调整；否则在小根层作小顶堆调整。
2）取出最小的数
也和普通堆相似，取堆头元素并把队尾元素放在堆头再调整堆。以堆头即第一层为小层为例：先和儿子比较（如果有儿子），如果比儿子大（儿子层是大层），和该儿子交换。
然后，如果有孙子，则在孙子层（小层）4个元素中找出最小的，与之交换，则在该孙子位置的情况和调整开始时堆头的情况是一样的，所以在该位置继续上面的调整过程。
3）取出最大的数
以第一层为小层为例：比较堆头的两个儿子谁大，取出作为最大的数，把堆尾元素填到该位置，在该位置开始调整。调整的过程和取出最小数的调整过程是一致的，大小相反。
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
238
239
240
241
|
#pragma once
#include <math.h>
#include <stddef.h>
#include <iostream>
using namespace std;
template <typename T>
class MinMaxHeap
{
public:
MinMaxHeap(int sz)
{
n = 0;
maxSize = sz;
_heap = new T[sz + 1];
}
void push(const T &x);
T popMin();
T popMax();
void printRaw()
{
for (int i = 1; i <= n; i++)
cout << _heap[i] << " ";
cout << endl;
}
private:
int level(int p)
{
if ((int)(log(p * 1.0) / log(2.0)) % 2 == 1)
return MAX;
else
return MIN;
}
void VerifyMax(int, const T &);
void VerifyMin(int, const T &);
int MinChildGrandChild(int pos);
int MaxChildGrandChild(int pos);
private:
T *_heap;
int maxSize, n;
static const int MIN = 0;
static const int MAX = 1;
};
template<typename T>
void MinMaxHeap<T>::push(const T &x )
{
if (n == maxSize )
{
//MinMaxFull( );
throw;
}
n++;
int p = n / 2; //p is new node's parent
if (!p)
{
_heap[1] = x;
return;
}
switch (level(p))
{
case MIN:
if (x < _heap[p]) // 沿着最小层检查
{
_heap[n] = _heap[p];
VerifyMin(p, x);
}
else VerifyMax(n, x); // 沿着最大层检查
break;
case MAX:
if (x > _heap[p]) // 沿着最大层检查
{
_heap[n] = _heap[p];
VerifyMax(p, x);
}
else VerifyMin(n, x); // 沿着最小层检查
break;
} //switch结束
} // Insert结束
template<typename T>
void MinMaxHeap<T>::VerifyMax(int i, const T &x )
{
// 沿着从最大结点i
// 到根结点的路径检查最大结点，将x插入正确位置
for (int gp = i / 4; gp && (x > _heap[gp]); gp /= 4) // gp是 i的祖父
{
_heap[i] = _heap[gp]; // 将_heap[gp]移到_heap[i]
i = gp;
}
_heap[i] = x; // 将x插入结点i
}
template<typename T>
void MinMaxHeap<T>::VerifyMin(int i, const T &x )
{
// 沿着从最小结点i
// 到根结点的路径检查最小结点，将x插入正确位置
for (int gp = i / 4; gp && (x < _heap[gp]); gp /= 4) // gp是 i的祖父
{
_heap[i] = _heap[gp]; // 将_heap[gp]移到_heap[i]
i = gp;
}
_heap[i] = x; // 将x插入结点i
}
template <class Type>
int MinMaxHeap<Type>::MinChildGrandChild(int i)
{
int temp[6] = {2*i, 2*i+1, 2*i*2, 2*i*2+1, (2*i+1)*2, (2*i+1)*2+1 };
if (2 * i > n) return 0;
int minVal = _heap[2 * i];
int minIndex = 2 * i;
for (int j = 1; j < 6; j++)
{
if(temp[j] <= n)
{
if (_heap[temp[j]] < minVal)
{
minVal = _heap[temp[j]];
minIndex = temp[j];
}
}
else break;
}
return minIndex;
}
template<typename T>
T MinMaxHeap<T>::popMin() // 从最小最大堆中删除并返回最小元素
{
if (!n)
{
//MinMaxEmpty( );
throw;
}
_heap[0] = INT_MAX;
T y = _heap[1]; // 保存根元素
T x = _heap[n--];
int i = 1, j = n / 2; // 为重新插入x作初始化，寻找插入x的位置
while (i <= j) // i 有子女，情况(2)
{
int k = MinChildGrandChild(i);
if (x <= _heap[k])
break; // 情况 2(a)，可将x 插入_heap[i]
else //情况2(b)或 (c)
{
_heap[i] = _heap[k];
if (k <= 2 * i + 1) // k 是i的子女，情况2(b)
{
i = k; // 可将x插入_heap[k]
break;
}
else // k是i的孙子女，情况2(c)
{
int p = k / 2; // p是k的双亲
if (x > _heap[p])
{
T t = _heap[p]; _heap[p] = x; x = t;
}
} // if (k<=2*i+1)结束
i = k;
} //if (x.key<=_heap[k].key)结束
} // while结束
_heap[i] = x; // 注意，即使现在n == 0，对_heap[1] 赋值也没错，这样简化边界判断
return y;
}
template <typename T>
int MinMaxHeap<T>::MaxChildGrandChild(int i)
{
int temp[6] = {2*i, 2*i+1, 2*i*2, 2*i*2+1, (2*i+1)*2, (2*i+1)*2+1 };
if (2 * i > n) return 0;
int maxVal = _heap[2 * i];
int maxIndex = 2 * i;
for (int j = 1; j < 6; j++)
{
if(temp[j] <= n)
{
if (_heap[temp[j]] > maxVal)
{
maxVal = _heap[temp[j]];
maxIndex = temp[j];
}
}
else break;
}
return maxIndex;
}
template<typename T>
T MinMaxHeap<T>::popMax() // 从最小最大堆中删除并返回最大元素
{
if (!n)
{
//MinMaxEmpty( );
throw;
}
if (n == 1) { n--; return _heap[1]; }
if (n == 2) { n--; return _heap[2]; }
int i = _heap[2] > _heap[3] ? 2 : 3;
T y = _heap[i]; // 保存根元素
T x = _heap[n--];
int j = n / 2; // 为重新插入x作初始化，寻找插入x的位置
_heap[0] = INT_MIN;
while (i <= j) // i 有子女，情况(2)
{
int k = MaxChildGrandChild(i);
if (x >= _heap[k])
break; // 情况 2(a)，可将x 插入_heap[i]
else //情况2(b)或 (c)
{
_heap[i] = _heap[k];
if (k <= 2 * i + 1) // k 是i的子女，情况2(b)
{
i = k; // 可将x插入_heap[k]
break;
}
else // k是i的孙子女，情况2(c)
{
int p = k / 2; // p是k的双亲
if (x < _heap[p])
{
T t = _heap[p]; _heap[p] = x; x = t;
}
} // if (k<=2*i+1)结束
i = k;
} //if (x.key<=_heap[k].key)结束
} // while结束
_heap[i] = x; // 注意，即使现在n == 0，对_heap[1] 赋值也没错，这样简化边界判断
return y;
}
|
参考
http://arxiv.org/ftp/cs/papers/0007/0007043.pdf
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf
https://github.com/brownhead/minmaxheap-cpp