Claim
t_insert = O(1) amortized
t_decrease-key = O(1) amortized
t_delete-min = O(log n) amortized
The potential function
Φ(H) = trees(H) + 2 · marks(H)
where trees(H) is the number of top-level trees and marks(H) the number of marked nodes 1:00:59, 1:02:05.
- Origin of such functions: they are engineered to make the proof work. Look at what changes after an operation — the tree count, and which nodes gain or lose marks — then pick constants that bound everything by the target
1:02:05,1:02:36,1:02:53.
Insert
- Actual cost:
O(1)— append to the root list1:03:18. Δtrees = +1,Δmarks = 0, soΔΦ = 11:04:00.- Amortized: constant
1:04:00.
Delete-min
- Actual cost:
O(t)wheretis the number of trees — the entire root list is scanned to find the min and to consolidate1:04:32,1:05:21. Δmarks ≤ 0: delete-min marks nothing, and the deleted min might itself have been marked1:06:00,1:06:22,1:06:42.Δtrees = t' − t, so thetterms cancel and the amortized cost isO(t')1:06:42.- Consolidation re-enforces the binomial-heap invariant of at most one tree per rank, so
t' ≤ max rank ≤ O(log n)via the Fibonacci growth bound1:06:42,1:07:27,1:07:49. - Amortized:
O(log n).
Decrease-key
Case 1 — no cut (the new key does not violate heap order) 1:08:07, 1:08:49:
- Actual cost
O(1);Δtrees = 0,Δmarks = 0;ΔΦ = 0⟹ constant.
Case 2 — c > 0 cascading cuts 1:09:44, 1:10:04:
| Term | Value |
|---|---|
| Actual cost | O(c) 1:10:26 |
Δtrees | +c — each cut creates a new top-level tree 1:10:26 |
2 · Δmarks | ≤ −2c + O(1) — each cut node clears its own mark, and at most one new mark is set (on the topmost surviving parent) 1:10:58, 1:11:35 |
The +c and −2c leave a negative leading term, so the total is constant 1:10:58.
Worked sanity check for c = 1: cutting x means x's parent was not previously marked, so the parent becomes marked (+1) while x's own mark is cleared on the move (−1, if it had one) — net change in marked items is not an increase 1:11:35, 1:12:00, 1:12:31.