container/heap: avoid use of the term "heap invariants"

[codesoap]

Go version

go version go1.21.1 openbsd/amd64

Issue

In the documentation of the Init function as well as the Interface interface and within the PriorityQueue example the term "heap invariants" is used. Maybe it is because I lack the academic background, but the term confused me when trying to understand the purpose of the Init function.

After some further reading I now understand, that it basically just means that the Init function establishes a correctly "sorted" heap from an "unsorted" input. I assume, that "sorting" is not the correct term to use and "establishing invariants" is a formally correct way to describe what Init does. However, I feel like easier language could be used to describe the function of Init and thus ease the understanding of the package.

[adonovan]

The first part of the package documentation says:

A heap is a tree with the property that each node is the minimum-valued node in its subtree.

So how about we document Init thus:

Init reorders the elements of the sequence to establish the heap property.

and replace "heap invariants" with "heap property" throughout?

Feel free to send a CL.

[codesoap]

Thanks for chiming in, @adonovan ! I have slightly adapted your suggestion and created a PR.

I have excluded the mention of a "sequence", since it is my understanding that a heap could be implemented with, e.g., a tree data structure, which is (to my knowledge) not considered a sequence.

Even though it might just be a small improvement, I feel like "heap property" will be more commonly understood than "heap invariants". Mentioning that the Init function reorders elements will likely further improve the readers understanding of what the function does.

[gopherbot]

Change https://go.dev/cl/562295 mentions this issue: container/heap: avoid the term "heap invariants"

[ianlancetaylor]

I really think "heap invariant" is fine.

[adonovan]

I'm fine with either, but Ian is usually right. "Invariant" is an important word to know, and if you learned it from this package, maybe that's no bad thing. Sorry for the churn.

[codesoap]

Alright; no hard feelings. Maybe the term is more commonly known than I'm aware and it was just a personal gap in education.