search

pllk / cphb

Competitive Programmer's Handbook
2.94k stars 354 forks source link

Chapter 13: Constant Time Lookup of Next Node #85

Open christopher-besch opened 3 years ago

christopher-besch commented 3 years ago

Isn't the lookup time of the next node constant instead of logarithmic? Current version:

Using a priority queue, the next node to be processed can be retrieved in logarithmic time.

Referring to cppreference.com:

A priority queue [...] provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

Referring to Page 43:

A priority queue maintains a set of elements [...] and retrieval takes O(1) time.

apronchenkov commented 2 years ago

I think it depends on the interpretation of "retrieved" -- if it includes taking out the node from the queue, it's logarithmic time for heap.

Maybe the fix should be in the chapter 4, something like: "Insertion and removal take O(logn) time, and finding the maximum takes O(1) time.

christopher-besch commented 2 years ago

That makes sense; thanks for clearing that up for me.

I've implemented the suggested changes and replaced retrieve with lookup. What do you say?