Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
codesoap opened this issue Feb 3, 2024 · 6 comments
Closed

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

codesoap opened this issue Feb 3, 2024 · 6 comments
Labels
Documentation NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.

Comments

@codesoap
Copy link
Contributor

codesoap commented Feb 3, 2024

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.
@seankhliao seankhliao added Documentation NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Feb 3, 2024
@adonovan
Copy link
Member

adonovan commented Feb 5, 2024 •
edited

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 codesoap mentioned this issue Feb 6, 2024
Closed
@codesoap
Copy link
Contributor Author

codesoap commented Feb 6, 2024

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
Copy link

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

@ianlancetaylor
Copy link
Contributor

I really think "heap invariant" is fine.

@adonovan
Copy link
Member

adonovan commented Feb 7, 2024

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
Copy link
Contributor Author

codesoap commented Feb 7, 2024

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

@ianlancetaylor ianlancetaylor closed this as not planned Won't fix, can't repro, duplicate, stale Feb 7, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Documentation NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

container/heap: avoid the term "heap invariants" codesoap/go
5 participants
@ianlancetaylor @adonovan @gopherbot @seankhliao @codesoap