Working Set Property

Working Set

对于在 \(x\) 插入后和弹出前的时间段内的某一时刻 \(t\), 定义 \(W_{x,t}\) 为在 \(x\) 之后插入并且在时间 \(t\) 仍在堆中的元素

定义使得 \(W_{x,t}\) 最大的时间为 \(t_0\), 则 \(W_{x,t_0}\) 记为 \(W_x\), 为 \(x\) 的 Working Set

Property

一个类 Fibonacci 堆有 Working Set Property, 如果满足

1. \(\text{INSERT, FINDMIN, DECREASEKEY}\) 是 \(O(1)\) 的

2. \(\text{DELETEMIN}\) 是 \(O(1+\log|W_x|)\) 的

---

参考:

1.Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps