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

Collections documentation could mention performance of BinaryHeap impl #47976

Closed
Ryman opened this issue Feb 2, 2018 · 1 comment · Fixed by #60952
Closed

Collections documentation could mention performance of BinaryHeap impl #47976

Ryman opened this issue Feb 2, 2018 · 1 comment · Fixed by #60952
Labels
A-collections Area: std::collections. A-docs Area: documentation for any part of the project, including the compiler, standard library, and tools C-enhancement Category: An issue proposing an enhancement or a PR with one. E-medium Call for participation: Medium difficulty. Experience needed to fix: Intermediate. P-medium Medium priority

Comments

@Ryman
Copy link
Contributor

Ryman commented Feb 2, 2018

I can't seem to find anything similar to the docs outlined here for BinaryHeap so I'm left to assume it aligns with the usual bounds as mentioned on wikipedia. It would be good if that information was available either in the collection overview or in the docs for BinaryHeap itself.
@cuviper cuviper added C-enhancement Category: An issue proposing an enhancement or a PR with one. A-collections Area: std::collections. A-docs Area: documentation for any part of the project, including the compiler, standard library, and tools labels Feb 3, 2018
@steveklabnik steveklabnik added the E-medium Call for participation: Medium difficulty. Experience needed to fix: Intermediate. label May 29, 2018
@steveklabnik steveklabnik added the P-medium Medium priority label Dec 27, 2018
@DevQps
Copy link
Contributor

DevQps commented Apr 4, 2019

I hope to create a PR for this somewhere today, adding the performance (big O-notation) characteristics to the collection page.

@DevQps DevQps mentioned this issue Apr 4, 2019
Closed
@dtolnay dtolnay mentioned this issue May 19, 2019
Merged
Centril added a commit to Centril/rust that referenced this issue May 20, 2019
@Centril
Rollup merge of rust-lang#60952 - dtolnay:heap, r=Amanieu
864e7a9 
Document BinaryHeap time complexity

I went into some detail on the time complexity of `push` because it is relevant for using BinaryHeap efficiently -- specifically that you should avoid pushing many elements in ascending order when possible.

r? @Amanieu
Closes rust-lang#47976. Closes rust-lang#59698.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-collections Area: std::collections. A-docs Area: documentation for any part of the project, including the compiler, standard library, and tools C-enhancement Category: An issue proposing an enhancement or a PR with one. E-medium Call for participation: Medium difficulty. Experience needed to fix: Intermediate. P-medium Medium priority
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Document BinaryHeap time complexity dtolnay/rust
Documented BinaryHeap performance. DevQps/rust
4 participants
@steveklabnik @cuviper @Ryman @DevQps