# Python code coverage for Modules/_heapqmodule.c

# | count | content |
---|---|---|

1 | n/a | /* Drop in replacement for heapq.py |

2 | n/a | |

3 | n/a | C implementation derived directly from heapq.py in Py2.3 |

4 | n/a | which was written by Kevin O'Connor, augmented by Tim Peters, |

5 | n/a | annotated by FranÃ§ois Pinard, and converted to C by Raymond Hettinger. |

6 | n/a | |

7 | n/a | */ |

8 | n/a | |

9 | n/a | #include "Python.h" |

10 | n/a | |

11 | n/a | static int |

12 | n/a | siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) |

13 | n/a | { |

14 | n/a | PyObject *newitem, *parent, **arr; |

15 | n/a | Py_ssize_t parentpos, size; |

16 | n/a | int cmp; |

17 | n/a | |

18 | n/a | assert(PyList_Check(heap)); |

19 | n/a | size = PyList_GET_SIZE(heap); |

20 | n/a | if (pos >= size) { |

21 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

22 | n/a | return -1; |

23 | n/a | } |

24 | n/a | |

25 | n/a | /* Follow the path to the root, moving parents down until finding |

26 | n/a | a place newitem fits. */ |

27 | n/a | arr = _PyList_ITEMS(heap); |

28 | n/a | newitem = arr[pos]; |

29 | n/a | while (pos > startpos) { |

30 | n/a | parentpos = (pos - 1) >> 1; |

31 | n/a | parent = arr[parentpos]; |

32 | n/a | cmp = PyObject_RichCompareBool(newitem, parent, Py_LT); |

33 | n/a | if (cmp < 0) |

34 | n/a | return -1; |

35 | n/a | if (size != PyList_GET_SIZE(heap)) { |

36 | n/a | PyErr_SetString(PyExc_RuntimeError, |

37 | n/a | "list changed size during iteration"); |

38 | n/a | return -1; |

39 | n/a | } |

40 | n/a | if (cmp == 0) |

41 | n/a | break; |

42 | n/a | arr = _PyList_ITEMS(heap); |

43 | n/a | parent = arr[parentpos]; |

44 | n/a | newitem = arr[pos]; |

45 | n/a | arr[parentpos] = newitem; |

46 | n/a | arr[pos] = parent; |

47 | n/a | pos = parentpos; |

48 | n/a | } |

49 | n/a | return 0; |

50 | n/a | } |

51 | n/a | |

52 | n/a | static int |

53 | n/a | siftup(PyListObject *heap, Py_ssize_t pos) |

54 | n/a | { |

55 | n/a | Py_ssize_t startpos, endpos, childpos, limit; |

56 | n/a | PyObject *tmp1, *tmp2, **arr; |

57 | n/a | int cmp; |

58 | n/a | |

59 | n/a | assert(PyList_Check(heap)); |

60 | n/a | endpos = PyList_GET_SIZE(heap); |

61 | n/a | startpos = pos; |

62 | n/a | if (pos >= endpos) { |

63 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

64 | n/a | return -1; |

65 | n/a | } |

66 | n/a | |

67 | n/a | /* Bubble up the smaller child until hitting a leaf. */ |

68 | n/a | arr = _PyList_ITEMS(heap); |

69 | n/a | limit = endpos >> 1; /* smallest pos that has no child */ |

70 | n/a | while (pos < limit) { |

71 | n/a | /* Set childpos to index of smaller child. */ |

72 | n/a | childpos = 2*pos + 1; /* leftmost child position */ |

73 | n/a | if (childpos + 1 < endpos) { |

74 | n/a | cmp = PyObject_RichCompareBool( |

75 | n/a | arr[childpos], |

76 | n/a | arr[childpos + 1], |

77 | n/a | Py_LT); |

78 | n/a | if (cmp < 0) |

79 | n/a | return -1; |

80 | n/a | childpos += ((unsigned)cmp ^ 1); /* increment when cmp==0 */ |

81 | n/a | arr = _PyList_ITEMS(heap); /* arr may have changed */ |

82 | n/a | if (endpos != PyList_GET_SIZE(heap)) { |

83 | n/a | PyErr_SetString(PyExc_RuntimeError, |

84 | n/a | "list changed size during iteration"); |

85 | n/a | return -1; |

86 | n/a | } |

87 | n/a | } |

88 | n/a | /* Move the smaller child up. */ |

89 | n/a | tmp1 = arr[childpos]; |

90 | n/a | tmp2 = arr[pos]; |

91 | n/a | arr[childpos] = tmp2; |

92 | n/a | arr[pos] = tmp1; |

93 | n/a | pos = childpos; |

94 | n/a | } |

95 | n/a | /* Bubble it up to its final resting place (by sifting its parents down). */ |

96 | n/a | return siftdown(heap, startpos, pos); |

97 | n/a | } |

98 | n/a | |

99 | n/a | static PyObject * |

100 | n/a | heappush(PyObject *self, PyObject *args) |

101 | n/a | { |

102 | n/a | PyObject *heap, *item; |

103 | n/a | |

104 | n/a | if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item)) |

105 | n/a | return NULL; |

106 | n/a | |

107 | n/a | if (!PyList_Check(heap)) { |

108 | n/a | PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); |

109 | n/a | return NULL; |

110 | n/a | } |

111 | n/a | |

112 | n/a | if (PyList_Append(heap, item)) |

113 | n/a | return NULL; |

114 | n/a | |

115 | n/a | if (siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1)) |

116 | n/a | return NULL; |

117 | n/a | Py_RETURN_NONE; |

118 | n/a | } |

119 | n/a | |

120 | n/a | PyDoc_STRVAR(heappush_doc, |

121 | n/a | "heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant."); |

122 | n/a | |

123 | n/a | static PyObject * |

124 | n/a | heappop_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t)) |

125 | n/a | { |

126 | n/a | PyObject *lastelt, *returnitem; |

127 | n/a | Py_ssize_t n; |

128 | n/a | |

129 | n/a | if (!PyList_Check(heap)) { |

130 | n/a | PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); |

131 | n/a | return NULL; |

132 | n/a | } |

133 | n/a | |

134 | n/a | /* raises IndexError if the heap is empty */ |

135 | n/a | n = PyList_GET_SIZE(heap); |

136 | n/a | if (n == 0) { |

137 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

138 | n/a | return NULL; |

139 | n/a | } |

140 | n/a | |

141 | n/a | lastelt = PyList_GET_ITEM(heap, n-1) ; |

142 | n/a | Py_INCREF(lastelt); |

143 | n/a | if (PyList_SetSlice(heap, n-1, n, NULL)) { |

144 | n/a | Py_DECREF(lastelt); |

145 | n/a | return NULL; |

146 | n/a | } |

147 | n/a | n--; |

148 | n/a | |

149 | n/a | if (!n) |

150 | n/a | return lastelt; |

151 | n/a | returnitem = PyList_GET_ITEM(heap, 0); |

152 | n/a | PyList_SET_ITEM(heap, 0, lastelt); |

153 | n/a | if (siftup_func((PyListObject *)heap, 0)) { |

154 | n/a | Py_DECREF(returnitem); |

155 | n/a | return NULL; |

156 | n/a | } |

157 | n/a | return returnitem; |

158 | n/a | } |

159 | n/a | |

160 | n/a | static PyObject * |

161 | n/a | heappop(PyObject *self, PyObject *heap) |

162 | n/a | { |

163 | n/a | return heappop_internal(heap, siftup); |

164 | n/a | } |

165 | n/a | |

166 | n/a | PyDoc_STRVAR(heappop_doc, |

167 | n/a | "Pop the smallest item off the heap, maintaining the heap invariant."); |

168 | n/a | |

169 | n/a | static PyObject * |

170 | n/a | heapreplace_internal(PyObject *args, int siftup_func(PyListObject *, Py_ssize_t)) |

171 | n/a | { |

172 | n/a | PyObject *heap, *item, *returnitem; |

173 | n/a | |

174 | n/a | if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item)) |

175 | n/a | return NULL; |

176 | n/a | |

177 | n/a | if (!PyList_Check(heap)) { |

178 | n/a | PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); |

179 | n/a | return NULL; |

180 | n/a | } |

181 | n/a | |

182 | n/a | if (PyList_GET_SIZE(heap) == 0) { |

183 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

184 | n/a | return NULL; |

185 | n/a | } |

186 | n/a | |

187 | n/a | returnitem = PyList_GET_ITEM(heap, 0); |

188 | n/a | Py_INCREF(item); |

189 | n/a | PyList_SET_ITEM(heap, 0, item); |

190 | n/a | if (siftup_func((PyListObject *)heap, 0)) { |

191 | n/a | Py_DECREF(returnitem); |

192 | n/a | return NULL; |

193 | n/a | } |

194 | n/a | return returnitem; |

195 | n/a | } |

196 | n/a | |

197 | n/a | static PyObject * |

198 | n/a | heapreplace(PyObject *self, PyObject *args) |

199 | n/a | { |

200 | n/a | return heapreplace_internal(args, siftup); |

201 | n/a | } |

202 | n/a | |

203 | n/a | PyDoc_STRVAR(heapreplace_doc, |

204 | n/a | "heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\ |

205 | n/a | \n\ |

206 | n/a | This is more efficient than heappop() followed by heappush(), and can be\n\ |

207 | n/a | more appropriate when using a fixed-size heap. Note that the value\n\ |

208 | n/a | returned may be larger than item! That constrains reasonable uses of\n\ |

209 | n/a | this routine unless written as part of a conditional replacement:\n\n\ |

210 | n/a | if item > heap[0]:\n\ |

211 | n/a | item = heapreplace(heap, item)\n"); |

212 | n/a | |

213 | n/a | static PyObject * |

214 | n/a | heappushpop(PyObject *self, PyObject *args) |

215 | n/a | { |

216 | n/a | PyObject *heap, *item, *returnitem; |

217 | n/a | int cmp; |

218 | n/a | |

219 | n/a | if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item)) |

220 | n/a | return NULL; |

221 | n/a | |

222 | n/a | if (!PyList_Check(heap)) { |

223 | n/a | PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); |

224 | n/a | return NULL; |

225 | n/a | } |

226 | n/a | |

227 | n/a | if (PyList_GET_SIZE(heap) == 0) { |

228 | n/a | Py_INCREF(item); |

229 | n/a | return item; |

230 | n/a | } |

231 | n/a | |

232 | n/a | cmp = PyObject_RichCompareBool(PyList_GET_ITEM(heap, 0), item, Py_LT); |

233 | n/a | if (cmp < 0) |

234 | n/a | return NULL; |

235 | n/a | if (cmp == 0) { |

236 | n/a | Py_INCREF(item); |

237 | n/a | return item; |

238 | n/a | } |

239 | n/a | |

240 | n/a | if (PyList_GET_SIZE(heap) == 0) { |

241 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

242 | n/a | return NULL; |

243 | n/a | } |

244 | n/a | |

245 | n/a | returnitem = PyList_GET_ITEM(heap, 0); |

246 | n/a | Py_INCREF(item); |

247 | n/a | PyList_SET_ITEM(heap, 0, item); |

248 | n/a | if (siftup((PyListObject *)heap, 0)) { |

249 | n/a | Py_DECREF(returnitem); |

250 | n/a | return NULL; |

251 | n/a | } |

252 | n/a | return returnitem; |

253 | n/a | } |

254 | n/a | |

255 | n/a | PyDoc_STRVAR(heappushpop_doc, |

256 | n/a | "heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\ |

257 | n/a | from the heap. The combined action runs more efficiently than\n\ |

258 | n/a | heappush() followed by a separate call to heappop()."); |

259 | n/a | |

260 | n/a | static Py_ssize_t |

261 | n/a | keep_top_bit(Py_ssize_t n) |

262 | n/a | { |

263 | n/a | int i = 0; |

264 | n/a | |

265 | n/a | while (n > 1) { |

266 | n/a | n >>= 1; |

267 | n/a | i++; |

268 | n/a | } |

269 | n/a | return n << i; |

270 | n/a | } |

271 | n/a | |

272 | n/a | /* Cache friendly version of heapify() |

273 | n/a | ----------------------------------- |

274 | n/a | |

275 | n/a | Build-up a heap in O(n) time by performing siftup() operations |

276 | n/a | on nodes whose children are already heaps. |

277 | n/a | |

278 | n/a | The simplest way is to sift the nodes in reverse order from |

279 | n/a | n//2-1 to 0 inclusive. The downside is that children may be |

280 | n/a | out of cache by the time their parent is reached. |

281 | n/a | |

282 | n/a | A better way is to not wait for the children to go out of cache. |

283 | n/a | Once a sibling pair of child nodes have been sifted, immediately |

284 | n/a | sift their parent node (while the children are still in cache). |

285 | n/a | |

286 | n/a | Both ways build child heaps before their parents, so both ways |

287 | n/a | do the exact same number of comparisons and produce exactly |

288 | n/a | the same heap. The only difference is that the traversal |

289 | n/a | order is optimized for cache efficiency. |

290 | n/a | */ |

291 | n/a | |

292 | n/a | static PyObject * |

293 | n/a | cache_friendly_heapify(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t)) |

294 | n/a | { |

295 | n/a | Py_ssize_t i, j, m, mhalf, leftmost; |

296 | n/a | |

297 | n/a | m = PyList_GET_SIZE(heap) >> 1; /* index of first childless node */ |

298 | n/a | leftmost = keep_top_bit(m + 1) - 1; /* leftmost node in row of m */ |

299 | n/a | mhalf = m >> 1; /* parent of first childless node */ |

300 | n/a | |

301 | n/a | for (i = leftmost - 1 ; i >= mhalf ; i--) { |

302 | n/a | j = i; |

303 | n/a | while (1) { |

304 | n/a | if (siftup_func((PyListObject *)heap, j)) |

305 | n/a | return NULL; |

306 | n/a | if (!(j & 1)) |

307 | n/a | break; |

308 | n/a | j >>= 1; |

309 | n/a | } |

310 | n/a | } |

311 | n/a | |

312 | n/a | for (i = m - 1 ; i >= leftmost ; i--) { |

313 | n/a | j = i; |

314 | n/a | while (1) { |

315 | n/a | if (siftup_func((PyListObject *)heap, j)) |

316 | n/a | return NULL; |

317 | n/a | if (!(j & 1)) |

318 | n/a | break; |

319 | n/a | j >>= 1; |

320 | n/a | } |

321 | n/a | } |

322 | n/a | Py_RETURN_NONE; |

323 | n/a | } |

324 | n/a | |

325 | n/a | static PyObject * |

326 | n/a | heapify_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t)) |

327 | n/a | { |

328 | n/a | Py_ssize_t i, n; |

329 | n/a | |

330 | n/a | if (!PyList_Check(heap)) { |

331 | n/a | PyErr_SetString(PyExc_TypeError, "heap argument must be a list"); |

332 | n/a | return NULL; |

333 | n/a | } |

334 | n/a | |

335 | n/a | /* For heaps likely to be bigger than L1 cache, we use the cache |

336 | n/a | friendly heapify function. For smaller heaps that fit entirely |

337 | n/a | in cache, we prefer the simpler algorithm with less branching. |

338 | n/a | */ |

339 | n/a | n = PyList_GET_SIZE(heap); |

340 | n/a | if (n > 2500) |

341 | n/a | return cache_friendly_heapify(heap, siftup_func); |

342 | n/a | |

343 | n/a | /* Transform bottom-up. The largest index there's any point to |

344 | n/a | looking at is the largest with a child index in-range, so must |

345 | n/a | have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is |

346 | n/a | (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If |

347 | n/a | n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest, |

348 | n/a | and that's again n//2-1. |

349 | n/a | */ |

350 | n/a | for (i = (n >> 1) - 1 ; i >= 0 ; i--) |

351 | n/a | if (siftup_func((PyListObject *)heap, i)) |

352 | n/a | return NULL; |

353 | n/a | Py_RETURN_NONE; |

354 | n/a | } |

355 | n/a | |

356 | n/a | static PyObject * |

357 | n/a | heapify(PyObject *self, PyObject *heap) |

358 | n/a | { |

359 | n/a | return heapify_internal(heap, siftup); |

360 | n/a | } |

361 | n/a | |

362 | n/a | PyDoc_STRVAR(heapify_doc, |

363 | n/a | "Transform list into a heap, in-place, in O(len(heap)) time."); |

364 | n/a | |

365 | n/a | static int |

366 | n/a | siftdown_max(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) |

367 | n/a | { |

368 | n/a | PyObject *newitem, *parent, **arr; |

369 | n/a | Py_ssize_t parentpos, size; |

370 | n/a | int cmp; |

371 | n/a | |

372 | n/a | assert(PyList_Check(heap)); |

373 | n/a | size = PyList_GET_SIZE(heap); |

374 | n/a | if (pos >= size) { |

375 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

376 | n/a | return -1; |

377 | n/a | } |

378 | n/a | |

379 | n/a | /* Follow the path to the root, moving parents down until finding |

380 | n/a | a place newitem fits. */ |

381 | n/a | arr = _PyList_ITEMS(heap); |

382 | n/a | newitem = arr[pos]; |

383 | n/a | while (pos > startpos) { |

384 | n/a | parentpos = (pos - 1) >> 1; |

385 | n/a | parent = arr[parentpos]; |

386 | n/a | cmp = PyObject_RichCompareBool(parent, newitem, Py_LT); |

387 | n/a | if (cmp < 0) |

388 | n/a | return -1; |

389 | n/a | if (size != PyList_GET_SIZE(heap)) { |

390 | n/a | PyErr_SetString(PyExc_RuntimeError, |

391 | n/a | "list changed size during iteration"); |

392 | n/a | return -1; |

393 | n/a | } |

394 | n/a | if (cmp == 0) |

395 | n/a | break; |

396 | n/a | arr = _PyList_ITEMS(heap); |

397 | n/a | parent = arr[parentpos]; |

398 | n/a | newitem = arr[pos]; |

399 | n/a | arr[parentpos] = newitem; |

400 | n/a | arr[pos] = parent; |

401 | n/a | pos = parentpos; |

402 | n/a | } |

403 | n/a | return 0; |

404 | n/a | } |

405 | n/a | |

406 | n/a | static int |

407 | n/a | siftup_max(PyListObject *heap, Py_ssize_t pos) |

408 | n/a | { |

409 | n/a | Py_ssize_t startpos, endpos, childpos, limit; |

410 | n/a | PyObject *tmp1, *tmp2, **arr; |

411 | n/a | int cmp; |

412 | n/a | |

413 | n/a | assert(PyList_Check(heap)); |

414 | n/a | endpos = PyList_GET_SIZE(heap); |

415 | n/a | startpos = pos; |

416 | n/a | if (pos >= endpos) { |

417 | n/a | PyErr_SetString(PyExc_IndexError, "index out of range"); |

418 | n/a | return -1; |

419 | n/a | } |

420 | n/a | |

421 | n/a | /* Bubble up the smaller child until hitting a leaf. */ |

422 | n/a | arr = _PyList_ITEMS(heap); |

423 | n/a | limit = endpos >> 1; /* smallest pos that has no child */ |

424 | n/a | while (pos < limit) { |

425 | n/a | /* Set childpos to index of smaller child. */ |

426 | n/a | childpos = 2*pos + 1; /* leftmost child position */ |

427 | n/a | if (childpos + 1 < endpos) { |

428 | n/a | cmp = PyObject_RichCompareBool( |

429 | n/a | arr[childpos + 1], |

430 | n/a | arr[childpos], |

431 | n/a | Py_LT); |

432 | n/a | if (cmp < 0) |

433 | n/a | return -1; |

434 | n/a | childpos += ((unsigned)cmp ^ 1); /* increment when cmp==0 */ |

435 | n/a | arr = _PyList_ITEMS(heap); /* arr may have changed */ |

436 | n/a | if (endpos != PyList_GET_SIZE(heap)) { |

437 | n/a | PyErr_SetString(PyExc_RuntimeError, |

438 | n/a | "list changed size during iteration"); |

439 | n/a | return -1; |

440 | n/a | } |

441 | n/a | } |

442 | n/a | /* Move the smaller child up. */ |

443 | n/a | tmp1 = arr[childpos]; |

444 | n/a | tmp2 = arr[pos]; |

445 | n/a | arr[childpos] = tmp2; |

446 | n/a | arr[pos] = tmp1; |

447 | n/a | pos = childpos; |

448 | n/a | } |

449 | n/a | /* Bubble it up to its final resting place (by sifting its parents down). */ |

450 | n/a | return siftdown_max(heap, startpos, pos); |

451 | n/a | } |

452 | n/a | |

453 | n/a | static PyObject * |

454 | n/a | heappop_max(PyObject *self, PyObject *heap) |

455 | n/a | { |

456 | n/a | return heappop_internal(heap, siftup_max); |

457 | n/a | } |

458 | n/a | |

459 | n/a | PyDoc_STRVAR(heappop_max_doc, "Maxheap variant of heappop."); |

460 | n/a | |

461 | n/a | static PyObject * |

462 | n/a | heapreplace_max(PyObject *self, PyObject *args) |

463 | n/a | { |

464 | n/a | return heapreplace_internal(args, siftup_max); |

465 | n/a | } |

466 | n/a | |

467 | n/a | PyDoc_STRVAR(heapreplace_max_doc, "Maxheap variant of heapreplace"); |

468 | n/a | |

469 | n/a | static PyObject * |

470 | n/a | heapify_max(PyObject *self, PyObject *heap) |

471 | n/a | { |

472 | n/a | return heapify_internal(heap, siftup_max); |

473 | n/a | } |

474 | n/a | |

475 | n/a | PyDoc_STRVAR(heapify_max_doc, "Maxheap variant of heapify."); |

476 | n/a | |

477 | n/a | static PyMethodDef heapq_methods[] = { |

478 | n/a | {"heappush", (PyCFunction)heappush, |

479 | n/a | METH_VARARGS, heappush_doc}, |

480 | n/a | {"heappushpop", (PyCFunction)heappushpop, |

481 | n/a | METH_VARARGS, heappushpop_doc}, |

482 | n/a | {"heappop", (PyCFunction)heappop, |

483 | n/a | METH_O, heappop_doc}, |

484 | n/a | {"heapreplace", (PyCFunction)heapreplace, |

485 | n/a | METH_VARARGS, heapreplace_doc}, |

486 | n/a | {"heapify", (PyCFunction)heapify, |

487 | n/a | METH_O, heapify_doc}, |

488 | n/a | {"_heappop_max", (PyCFunction)heappop_max, |

489 | n/a | METH_O, heappop_max_doc}, |

490 | n/a | {"_heapreplace_max",(PyCFunction)heapreplace_max, |

491 | n/a | METH_VARARGS, heapreplace_max_doc}, |

492 | n/a | {"_heapify_max", (PyCFunction)heapify_max, |

493 | n/a | METH_O, heapify_max_doc}, |

494 | n/a | {NULL, NULL} /* sentinel */ |

495 | n/a | }; |

496 | n/a | |

497 | n/a | PyDoc_STRVAR(module_doc, |

498 | n/a | "Heap queue algorithm (a.k.a. priority queue).\n\ |

499 | n/a | \n\ |

500 | n/a | Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\ |

501 | n/a | all k, counting elements from 0. For the sake of comparison,\n\ |

502 | n/a | non-existing elements are considered to be infinite. The interesting\n\ |

503 | n/a | property of a heap is that a[0] is always its smallest element.\n\ |

504 | n/a | \n\ |

505 | n/a | Usage:\n\ |

506 | n/a | \n\ |

507 | n/a | heap = [] # creates an empty heap\n\ |

508 | n/a | heappush(heap, item) # pushes a new item on the heap\n\ |

509 | n/a | item = heappop(heap) # pops the smallest item from the heap\n\ |

510 | n/a | item = heap[0] # smallest item on the heap without popping it\n\ |

511 | n/a | heapify(x) # transforms list into a heap, in-place, in linear time\n\ |

512 | n/a | item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\ |

513 | n/a | # new item; the heap size is unchanged\n\ |

514 | n/a | \n\ |

515 | n/a | Our API differs from textbook heap algorithms as follows:\n\ |

516 | n/a | \n\ |

517 | n/a | - We use 0-based indexing. This makes the relationship between the\n\ |

518 | n/a | index for a node and the indexes for its children slightly less\n\ |

519 | n/a | obvious, but is more suitable since Python uses 0-based indexing.\n\ |

520 | n/a | \n\ |

521 | n/a | - Our heappop() method returns the smallest item, not the largest.\n\ |

522 | n/a | \n\ |

523 | n/a | These two make it possible to view the heap as a regular Python list\n\ |

524 | n/a | without surprises: heap[0] is the smallest item, and heap.sort()\n\ |

525 | n/a | maintains the heap invariant!\n"); |

526 | n/a | |

527 | n/a | |

528 | n/a | PyDoc_STRVAR(__about__, |

529 | n/a | "Heap queues\n\ |

530 | n/a | \n\ |

531 | n/a | [explanation by Fran\xc3\xa7ois Pinard]\n\ |

532 | n/a | \n\ |

533 | n/a | Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\ |

534 | n/a | all k, counting elements from 0. For the sake of comparison,\n\ |

535 | n/a | non-existing elements are considered to be infinite. The interesting\n\ |

536 | n/a | property of a heap is that a[0] is always its smallest element.\n" |

537 | n/a | "\n\ |

538 | n/a | The strange invariant above is meant to be an efficient memory\n\ |

539 | n/a | representation for a tournament. The numbers below are `k', not a[k]:\n\ |

540 | n/a | \n\ |

541 | n/a | 0\n\ |

542 | n/a | \n\ |

543 | n/a | 1 2\n\ |

544 | n/a | \n\ |

545 | n/a | 3 4 5 6\n\ |

546 | n/a | \n\ |

547 | n/a | 7 8 9 10 11 12 13 14\n\ |

548 | n/a | \n\ |

549 | n/a | 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\ |

550 | n/a | \n\ |

551 | n/a | \n\ |

552 | n/a | In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\ |

553 | n/a | a usual binary tournament we see in sports, each cell is the winner\n\ |

554 | n/a | over the two cells it tops, and we can trace the winner down the tree\n\ |

555 | n/a | to see all opponents s/he had. However, in many computer applications\n\ |

556 | n/a | of such tournaments, we do not need to trace the history of a winner.\n\ |

557 | n/a | To be more memory efficient, when a winner is promoted, we try to\n\ |

558 | n/a | replace it by something else at a lower level, and the rule becomes\n\ |

559 | n/a | that a cell and the two cells it tops contain three different items,\n\ |

560 | n/a | but the top cell \"wins\" over the two topped cells.\n" |

561 | n/a | "\n\ |

562 | n/a | If this heap invariant is protected at all time, index 0 is clearly\n\ |

563 | n/a | the overall winner. The simplest algorithmic way to remove it and\n\ |

564 | n/a | find the \"next\" winner is to move some loser (let's say cell 30 in the\n\ |

565 | n/a | diagram above) into the 0 position, and then percolate this new 0 down\n\ |

566 | n/a | the tree, exchanging values, until the invariant is re-established.\n\ |

567 | n/a | This is clearly logarithmic on the total number of items in the tree.\n\ |

568 | n/a | By iterating over all items, you get an O(n ln n) sort.\n" |

569 | n/a | "\n\ |

570 | n/a | A nice feature of this sort is that you can efficiently insert new\n\ |

571 | n/a | items while the sort is going on, provided that the inserted items are\n\ |

572 | n/a | not \"better\" than the last 0'th element you extracted. This is\n\ |

573 | n/a | especially useful in simulation contexts, where the tree holds all\n\ |

574 | n/a | incoming events, and the \"win\" condition means the smallest scheduled\n\ |

575 | n/a | time. When an event schedule other events for execution, they are\n\ |

576 | n/a | scheduled into the future, so they can easily go into the heap. So, a\n\ |

577 | n/a | heap is a good structure for implementing schedulers (this is what I\n\ |

578 | n/a | used for my MIDI sequencer :-).\n" |

579 | n/a | "\n\ |

580 | n/a | Various structures for implementing schedulers have been extensively\n\ |

581 | n/a | studied, and heaps are good for this, as they are reasonably speedy,\n\ |

582 | n/a | the speed is almost constant, and the worst case is not much different\n\ |

583 | n/a | than the average case. However, there are other representations which\n\ |

584 | n/a | are more efficient overall, yet the worst cases might be terrible.\n" |

585 | n/a | "\n\ |

586 | n/a | Heaps are also very useful in big disk sorts. You most probably all\n\ |

587 | n/a | know that a big sort implies producing \"runs\" (which are pre-sorted\n\ |

588 | n/a | sequences, which size is usually related to the amount of CPU memory),\n\ |

589 | n/a | followed by a merging passes for these runs, which merging is often\n\ |

590 | n/a | very cleverly organised[1]. It is very important that the initial\n\ |

591 | n/a | sort produces the longest runs possible. Tournaments are a good way\n\ |

592 | n/a | to that. If, using all the memory available to hold a tournament, you\n\ |

593 | n/a | replace and percolate items that happen to fit the current run, you'll\n\ |

594 | n/a | produce runs which are twice the size of the memory for random input,\n\ |

595 | n/a | and much better for input fuzzily ordered.\n" |

596 | n/a | "\n\ |

597 | n/a | Moreover, if you output the 0'th item on disk and get an input which\n\ |

598 | n/a | may not fit in the current tournament (because the value \"wins\" over\n\ |

599 | n/a | the last output value), it cannot fit in the heap, so the size of the\n\ |

600 | n/a | heap decreases. The freed memory could be cleverly reused immediately\n\ |

601 | n/a | for progressively building a second heap, which grows at exactly the\n\ |

602 | n/a | same rate the first heap is melting. When the first heap completely\n\ |

603 | n/a | vanishes, you switch heaps and start a new run. Clever and quite\n\ |

604 | n/a | effective!\n\ |

605 | n/a | \n\ |

606 | n/a | In a word, heaps are useful memory structures to know. I use them in\n\ |

607 | n/a | a few applications, and I think it is good to keep a `heap' module\n\ |

608 | n/a | around. :-)\n" |

609 | n/a | "\n\ |

610 | n/a | --------------------\n\ |

611 | n/a | [1] The disk balancing algorithms which are current, nowadays, are\n\ |

612 | n/a | more annoying than clever, and this is a consequence of the seeking\n\ |

613 | n/a | capabilities of the disks. On devices which cannot seek, like big\n\ |

614 | n/a | tape drives, the story was quite different, and one had to be very\n\ |

615 | n/a | clever to ensure (far in advance) that each tape movement will be the\n\ |

616 | n/a | most effective possible (that is, will best participate at\n\ |

617 | n/a | \"progressing\" the merge). Some tapes were even able to read\n\ |

618 | n/a | backwards, and this was also used to avoid the rewinding time.\n\ |

619 | n/a | Believe me, real good tape sorts were quite spectacular to watch!\n\ |

620 | n/a | From all times, sorting has always been a Great Art! :-)\n"); |

621 | n/a | |

622 | n/a | |

623 | n/a | static struct PyModuleDef _heapqmodule = { |

624 | n/a | PyModuleDef_HEAD_INIT, |

625 | n/a | "_heapq", |

626 | n/a | module_doc, |

627 | n/a | -1, |

628 | n/a | heapq_methods, |

629 | n/a | NULL, |

630 | n/a | NULL, |

631 | n/a | NULL, |

632 | n/a | NULL |

633 | n/a | }; |

634 | n/a | |

635 | n/a | PyMODINIT_FUNC |

636 | n/a | PyInit__heapq(void) |

637 | n/a | { |

638 | n/a | PyObject *m, *about; |

639 | n/a | |

640 | n/a | m = PyModule_Create(&_heapqmodule); |

641 | n/a | if (m == NULL) |

642 | n/a | return NULL; |

643 | n/a | about = PyUnicode_DecodeUTF8(__about__, strlen(__about__), NULL); |

644 | n/a | PyModule_AddObject(m, "__about__", about); |

645 | n/a | return m; |

646 | n/a | } |

647 | n/a |