Binary Heap: Extract Max seems wrong: O(n log(n))
murraycu opened this issue · 1 comments
murraycu commented
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 commented
Incidentally, this seems to be correct on bigocheatsheet.com.