Skip to content

/ bigoref

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.

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

Binary Heap: Extract Max seems wrong: O(n log(n)) #5

Open
murraycu opened this issue Feb 15, 2016 · 1 comment
Open

Binary Heap: Extract Max seems wrong: O(n log(n)) #5

murraycu opened this issue Feb 15, 2016 · 1 comment

Comments

@murraycu
Copy link

@murraycu murraycu commented Feb 15, 2016

bigoref.com lists the average time complexity of Extract Max for a Binary Heap as O(n log(n)), but it should apparently be O(log(n), as it is on bigocheatsheet.com and in wikipedia:
https://en.wikipedia.org/wiki/Binary_heap#Extract

The other time complexities for binary heap seem wrong too. And for Binomial Heap too, I think,
@murraycu murraycu changed the title Binary Tree: Extract Max seems wrong: O(n log(n)) Binary Heap: Extract Max seems wrong: O(n log(n)) Feb 24, 2016
@murraycu
Copy link
Author

@murraycu murraycu commented Feb 24, 2016

Incidentally, this seems to be correct on bigocheatsheet.com.
jade-42 added a commit to jade-42/bigoref that referenced this issue Sep 21, 2017
@jade-42
Correct Binary Heap
Loading status checks…
6e52f45 
Corrected binary heap Big O per josem#5 and https://en.wikipedia.org/wiki/Binary_heap#Extract
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant
@murraycu