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

josem / bigoref

Big O Reference of common algorithms and data structures

MIT License

50 stars 10 forks source link

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

Open murraycu opened 8 years ago

murraycu commented 8 years ago

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 8 years ago

Incidentally, this seems to be correct on bigocheatsheet.com.