hard20 pts · first answer countsstacks-and-queues

Supporting decrease-key in a binary heap

You want a heap with a decreaseKey(item, newPriority) operation in O(log n). What extra structure do you need?

A.A second heap sorted by the opposite orderB.A linked list of items in insertion orderC.Nothing, the heap can find any item in O(log n)D.A map from each item to its current array index

Discussion 0

Join free to post in the discussion.

Supporting decrease-key in a binary heap

Discussion 0

Related questions