Skip to main content

Advanced Heaps and Amortized Analysis Workshop

Retrieval Prompts​

  1. State the structural invariant of a binomial heap in terms of n's binary representation.
  2. State the amortized bounds of a Fibonacci heap for insert, union, decrease-key, and extract-min.
  3. State the potential function used in the Fibonacci-heap analysis.
  4. State the three amortized-analysis methods and one sentence on when each is most natural.
  5. Write the identity amortized_i = actual_i + Delta Phi_i and name each term.

Compare and Distinguish​

Separate these pairs clearly:

  • binomial heap versus Fibonacci heap (what eager-vs-lazy means for each operation)
  • Fibonacci heap versus pairing heap (proven bound vs practical performance)
  • aggregate method versus potential method (which is more general and why)
  • worst-case bound versus amortized bound (what each guarantees)
  • average-case versus amortized (the difference between a probability distribution and a worst-case sequence)

Common Mistake Check​

For each statement, identify the error:

  1. "insert into a binomial heap is always O(1) because it just adds a B_0."
  2. "Fibonacci heaps give Dijkstra an asymptotic improvement for every graph."
  3. "An amortized O(1) operation is always fast; no single call can ever stall."
  4. "Aggregate analysis is strictly weaker than potential analysis for every data structure."
  5. "The Fibonacci-heap marked bit exists to speed up extract-min."

Mini Application​

Part A - Heap trace​

Starting from an empty binomial heap, insert 1, 3, 5, 7, 9, 11, 13, 15 one at a time. After each insert, record:

  1. the current value of n in binary
  2. the forest of binomial trees currently present (by order B_k)
  3. the number of tree-link operations performed

Verify that your running link count agrees with the amortized bound.

Part B - Fibonacci-heap derivation​

Given the Fibonacci-heap potential

Phi = (number of roots t(H)) + 2 * (number of marked non-root nodes m(H)),

compute the amortized cost for each operation below:

  1. insert(x) on a heap with t roots and m marks
  2. union(H1, H2) splicing root lists of sizes t1, t2
  3. decrease-key that cuts one node, with no cascade, from an unmarked parent
  4. decrease-key that cuts one node and triggers one cascading cut (parent was already marked)
  5. extract-min that exposes d children and reduces the root count from t to O(log n) after consolidation

State the result and the Delta Phi in each case.

Part C - Pick the heap​

For each scenario, choose binary, binomial, Fibonacci, or pairing heap and justify:

  1. shortest-path computation on a sparse graph with 10^7 edges
  2. MST on a dense graph with V^2 edges where V = 5,000
  3. a priority-queue-heavy simulation where decrease-key dominates the operation mix
  4. a code-golf competition where the simplest correct priority queue wins

Evidence Check​

This page is complete only if you can:

  • trace a full binomial-heap insert sequence by hand and predict the resulting forest
  • apply the Fibonacci-heap potential function to compute amortized cost for at least two distinct operations
  • decide between binary, binomial, Fibonacci, and pairing heaps for a stated operation mix
  • explain in one sentence why amortized is not average-case