Surprise Amortized-Complexity Practice!

The CHANGE-PRIORITY operation changes the priority of an item already in the priority queue (and adjusts accordingly).

For a binary heap, that adjustment would involve either floating the item up or sinking it down as necessary. In the worst case, it could take \( \Theta( \log{n} ) \) time.

Now, imagine that we heapify an array of \( n \) items and then change the priority of each item.

Binary Heap

First, performing HEAPIFY takes \( \Theta(n) \) time.

We know that CHANGE-PRIORITY takes \( \mathrm{O}( \log n ) \) time (no worse than logarithmic, but could be better).

So we are performing \( n \times \mathrm{O}( \log n ) \)-time operations. In total: \( \Theta(n) + \mathrm{O}( n \log n ) = \mathrm{O}( n \log n ) \) time.

Fibonacci Heap

There is another encoding of the priority-queue interface called a Fibonacci heap. The name comes from the fact that the Fibonacci sequence plays a role in the analysis of its complexity. (Not because it uses Fibonacci numbers in its implementation (it doesn't) and definitely not because it was invented by Fibonacci (who was born in the 1100s).)

Though the Fibonacci heap is often too complicated to be practical, its claim to fame is that it offers amortized \( \Theta(1) \) CHANGE-PRIORITY. It can also do HEAPIFY in \( \Theta(n) \) time.

We don't need to study this structure any more deeply than we have to analyze how it would impact the complexity of our sequence of operations.

Again, the HEAPIFY operation will take \( \Theta(n) \) time.

Then we perform \( n \) CHANGE-PRIORITY operations, which have amortized \( \Theta(1) \) time. We don't know how long each individual operation will take, but we know that the total complexity of all \( n \) will be \( \Theta(1) + \Theta(1) + \Theta(1) + \cdots + \Theta(1) = \Theta(n) \) time.

So, in total, we have \( \Theta(n) + \Theta(n) = \Theta(n) \) time.

(When logged in, completion status appears here.)

Previous Page Next Page