This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: discuss mark-as-invalid trick in heapq docs
Type: Stage:
Components: Documentation Versions: Python 3.1, Python 3.2, Python 2.7, Python 2.6
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: eric.smith, georg.brandl, jab, rhettinger
Priority: normal Keywords:

Created on 2010-01-18 22:07 by jab, last changed 2022-04-11 14:56 by admin. This issue is now closed.

Messages (5)
msg98034 - (view) Author: Joshua Bronson (jab) * Date: 2010-01-18 22:07
Though the heapq module does not support changing the priority of a particular element of the heap (a necessary operation for the A* search family of algorithms), such an element can be marked as invalid and a new element can be added with different priority. Any element marked as invalid that makes it to the top of the heap can simply be popped off and ignored.

Users who haven't seen this trick before might mistakenly think the heapq module does not provide sufficient operations to implement A* search.

Please see the recent thread on comp.lang.python for more background:
msg98035 - (view) Author: Eric V. Smith (eric.smith) * (Python committer) Date: 2010-01-18 22:17
Assigning to Raymond, per his request in the c.l.p. thread.
msg113226 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-08-08 01:17
Applied in r83793
Thanks for the suggestion.
msg113712 - (view) Author: Joshua Bronson (jab) * Date: 2010-08-12 22:09
Thanks for the great additions.
msg113718 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-08-12 22:57
You're welcome :-)
Date User Action Args
2022-04-11 14:56:56adminsetgithub: 51983
2010-08-12 22:57:26rhettingersetmessages: + msg113718
2010-08-12 22:09:04jabsetmessages: + msg113712
2010-08-08 01:17:32rhettingersetstatus: open -> closed
resolution: accepted
messages: + msg113226
2010-01-18 22:17:35eric.smithsetassignee: georg.brandl -> rhettinger

messages: + msg98035
nosy: + eric.smith
2010-01-18 22:07:46jabcreate