[issue32142] heapq.heappop - documentation misleading or doesn't work

[Cheryl Sabella]

Change by Cheryl Sabella :


--
resolution:  -> rejected
stage:  -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[Raymond Hettinger]

Raymond Hettinger  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[R. David Murray]

R. David Murray  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[Raymond Hettinger]

Change by Raymond Hettinger :


--
assignee: docs@python -> rhettinger
nosy: +rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[Scott Queen]

Scott Queen  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  wrote:

>
> abcdef  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 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[Eric V. Smith]

Eric V. Smith  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[abcdef]

abcdef  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[Eric V. Smith]

Eric V. Smith  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32142] heapq.heappop - documentation misleading or doesn't work

[Scott Queen]

New submission from Scott Queen :

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com