45 template<
typename Item>
61 bool mmless(
int i,
int j)
const 63 return data[heap[i]] < data[heap[j]];
67 bool mmexchange(
int i,
int j)
69 const int t = heap[i];
78 bool mmCmpExch(
int i,
int j)
80 return mmless(i, j) && mmexchange(i, j);
84 void minSortDown(
int i)
86 for (i *= 2; i <= minCt; i *= 2)
88 if (i < minCt && mmless(i + 1, i))
90 if (!mmCmpExch(i, i / 2))
96 void maxSortDown(
int i)
98 for (i *= 2; i >= -maxCt; i *= 2)
100 if (i > -maxCt && mmless(i, i - 1))
102 if (!mmCmpExch(i / 2, i))
109 bool minSortUp(
int i)
111 while (i > 0 && mmCmpExch(i, i / 2))
118 bool maxSortUp(
int i)
120 while (i < 0 && mmCmpExch(i / 2, i))
133 int size = N * (
sizeof(Item) +
sizeof(
int) * 2);
134 data = (Item*)malloc(
size);
135 pos = (
int*) (data + N);
136 heap = pos + N + (N / 2);
168 pos[nItems] = ((nItems + 1) / 2) * ((nItems & 1) ? -1 : 1);
169 heap[pos[nItems]] = nItems;
182 Item old = data[idx];
185 sz = std::min<int>(sz + 1, N);
188 if (minCt < (N - 1) / 2)
197 if (minSortUp(p) && mmCmpExch(0, -1))
211 if (maxSortUp(p) && minCt && mmCmpExch(1, 0))
216 if (maxCt && maxSortUp(-1))
218 if (minCt && minSortUp(1))
226 Item v = data[heap[0]];
229 v = (v + data[heap[-1]]) / 2;
void * memcpy(void *a, const void *b, size_t c)