Misleading comment "heap.sort() maintains the heap invariant"

[florensacc]

Documentation

In the fourth paragraph of the documentation says:
"""
These two make it possible to view the heap as a regular Python list without surprises: heap[0] is the smallest item, and heap.sort() maintains the heap invariant!
"""
This seems to suggest that heap.sort() does not change heap, although that's clearly not true:

heap = [1, 2, 4, 3]  # this is already a valid heap
heapq.heapify(heap)   # doesn't change `heap`
heap.sort()  # this is now `[1, 2, 3, 4]`!!

Linked PRs

• gh-114466: explicitly define heap invariant #117778
• [3.12] gh-114466: explicitly define heap invariant (GH-117778) #117835

[Eclips4]

cc @rhettinger

[gaogaotiantian]

I'm not the master of the language but "maintains the heap invariant" here means "it's still a heap" to me. I guess a possible ambiguity is that the variable itself is also heap - but all the variable heap is labeled specially (with dark background). So the "heap" here means the general concept "heap", not the variable heap.

[terryjreedy]

The confusion is interpreting 'heap invariant' as noun 'heap' that is kept adjective 'invariant', unchanged. It is meant be interpreted as a compount noun meaning the invariant that characterizes a heap. In other words, 'invariant' is the noun that in maintained and 'heap' is used as a noun-adjective that specified which invariant is maintained. 'Invariant' is a math and CS term meaning a condition that characterizes an math or information structure. Unless more than one person is confused, we could close this. The term 'heap invariant' should have been defined earlier in the doc. @florensacc , please check.

[hauntsaninja]

The docs do describe the invariant, but they don't use the term "heap invariant" when doing so. If. others are likely to be confused as well, maybe something like the following could be useful:

 Heaps are binary trees for which every parent node has a value less than or
-equal to any of its children.  This implementation uses arrays for which
+equal to any of its children.  We refer to this condition as the heap invariant.
+
+This implementation uses arrays for which

[florensacc]

Thanks for the comments, I see how the sentence is technically correct when understanding "invariant" as the noun and "heap" its noun-adjective. Defining "heap invariant" earlier like @hauntsaninja suggests would definitely help! And maybe we could also rephrase "and heap.sort() maintains the heap invariant!" as "and heap.sort() also satisfies the heap invariant!" or plainly "and heap.sort() is also a heap!".

[pochmann3]

"and heap.sort() is also a heap!".

It's not. It's None.

The Theory section btw already does use the term "invariant".

Wikipedia doesn't use "invariant" but "property", and "heap property" does seem to be the much more popular term, and "maintains the heap property" would avoid the ambiguity.

[hauntsaninja]

I think "invariant" is clear / standard enough, and since OP says it would help, I've opened a PR with my suggestion. Like terryjreedy says, unless we have evidence of more confusion, I don't see a need to make further changes.