[issue32142] heapq.heappop - documentation misleading or doesn't work
New submission from Scott Queen <scooter4j@gmail.com>: The documentation for heapq.heappop(heap) says: "Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0]." yet, in the following code, the resultant heap doesn't reflect the heap invariant: import heapq li = [5, 7, 9, 1, 4, 3] heapq.heapify(li) #change a couple values in the heap li[3] = 16 li[4] = 2 print (heapq.heappop(li)) print ("The heap after pop is : ",end="") print (list(li)) This prints: The heap after pop is : [3, 4, 9, 16, 2] The documentation implies to me that heapify would be called internally after heappop, but I may be misreading. Perhaps heappop could say that the heap invariant is maintained if the heap is properly sorted before the heappop invocation. ---------- assignee: docs@python components: Documentation messages: 307006 nosy: docs@python, scooter4j priority: normal severity: normal status: open title: heapq.heappop - documentation misleading or doesn't work type: behavior versions: Python 3.6 _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
Eric V. Smith <eric@trueblade.com> added the comment: The heap invariant is also required in order to even meet the documented behavior of returning the smallest item.
import heapq li = [5, 7, 9, 1, 4, 3] heapq.heapify(li) li [1, 4, 3, 7, 5, 9] li[2] = 0 heapq.heappop(li) 1 li [0, 4, 9, 7, 5]
I guess the argument could be made that docs say "from the heap", and by modifying the list yourself it's no longer a heap. ---------- nosy: +eric.smith _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
abcdef <x@mailinator.com> added the comment:
Perhaps heappop could say that the heap invariant is maintained if the heap is properly sorted before the heappop invocation.
Honestly I like this wording less. "Properly sorted" would suggest sorted in the sense of heap.sort() [as the docs refer to this earlier], but the array doesn't have to be sorted; it's enough if it's a heap. The function always maintains the invariant - this means that if the invariant is true as a precondition, it will be true as a postcondition. Maybe you have a different idea? ---------- nosy: +abcdef _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
Scott Queen <scooter4j@gmail.com> added the comment: Fair statement. "Properly sorted" was a poor choice. Seems that "if the invariant is true as a precondition, it will be true as a postcondition" is accurate and descriptive - maybe with a caution that modifying the list (heap) values by means other than the heapq functions are likely to render the invariant false (the latter phrase being for somewhat newbies like me who wouldn't realize this truth without having to learn it in the debugger). On Sun, Nov 26, 2017 at 10:51 AM, abcdef <report@bugs.python.org> wrote:
abcdef <x@mailinator.com> added the comment:
Perhaps heappop could say that the heap invariant is maintained if the heap is properly sorted before the heappop invocation.
Honestly I like this wording less. "Properly sorted" would suggest sorted in the sense of heap.sort() [as the docs refer to this earlier], but the array doesn't have to be sorted; it's enough if it's a heap. The function always maintains the invariant - this means that if the invariant is true as a precondition, it will be true as a postcondition. Maybe you have a different idea?
---------- nosy: +abcdef
_______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
Eric V. Smith <eric@trueblade.com> added the comment: By "sorted" I meant "sorted by the heap functions so as to maintain their invariants". I don't have any suggestion for the actual specific language to use. ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
Change by Raymond Hettinger <raymond.hettinger@gmail.com>: ---------- assignee: docs@python -> rhettinger nosy: +rhettinger _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
R. David Murray <rdmurray@bitdance.com> added the comment: I would suggested following the statement "To create a heap, use a list initialized to [], or you can transform a populated list into a heap via function heapify()." with "Any mutation of the list thereafter must maintain the heap invariant in order for the list to remain a heap." ---------- nosy: +r.david.murray _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
Raymond Hettinger <raymond.hettinger@gmail.com> added the comment: We could apply David Murray's suggested wording but I don't think it would actually help anyone. There are worked out examples from basic to advanced and a detailed section on the theory as well. ISTM, that prior to reading the docs, the OP likely already had an incorrect mental model that caused the misreading of "maintaining" as "restoring". For the most part, these docs have stood the test of time. I don't see any StackOverflow questions about this either. I recommend marking this as closed (the OP seems to now have a clear understanding of this so there isn't an open problem to be resolved). ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
Change by Cheryl Sabella <cheryl.sabella@gmail.com>: ---------- resolution: -> rejected stage: -> resolved status: open -> closed _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue32142> _______________________________________
participants (6)
-
abcdef -
Cheryl Sabella
-
Eric V. Smith
-
R. David Murray
-
Raymond Hettinger
-
Scott Queen