Template:堆运行时间
跳转到导航
跳转到搜索
Template:Incomplete 下面的时间复杂度中，[1]O(f)是一个渐近的上界，而Θ(f)是一个准确的上界（见大O符号）。函数名均假设该堆为最小堆。
| 操作 | 二叉[1] | 左偏 | 二项[1] | 斐波那契[1][2] | 配对[3] | Brodal[4]Template:Efn |
|---|---|---|---|---|---|---|
| find-min | Θ(1) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
| delete-min | Θ(log n) | Θ(log n) | Θ(log n) | O(log n)Template:Efn | O(log n)Template:Efn | O(log n) |
| insert | O(log n) | Θ(log n) | Θ(1)Template:Efn | Θ(1) | Θ(1) | Θ(1) |
| decrease-key | Θ(log n) | Θ(n) | Θ(log n) | Θ(1)Template:Efn | o(log n)Template:EfnTemplate:Efn | Θ(1) |
| merge | Θ(n) | Θ(log n) | O(log n)Template:Efn | Θ(1) | Θ(1) | Θ(1) |