假设我们得到：

• 由标准二进制堆 H 实现的 优先级队列（ 在数组上实现 ）
• n 当前堆大小

我们具有以下 插入 属性：

• W（n）= WorstCase（n）=Θ（lg n）（θ）。-> W（n）=Ω（lg n）且W（n）= O（lg n）
• A（n）= AverageCase（n）=Θ（lg n）（θ）。-> W（n）=Ω（lg n）且W（n）= O（lg n）
• B（n）= BestCase（n）=Θ（1）（θ）。-> W（n）=Ω（1）且W（n）= O（1）

所以对于 每种情况 ，我们都有

• T（n）=Ω（1）和T（n）= O（lg n）

最坏的情况是，当我们插入新的最小值时，堆必须遍历整个分支。

BestCase的情况是，对于最小堆（顶部堆最小），我们插入BIG（在更新分支上最大堆）值（因此，堆立即停止）。

您已经问过关于已经包含n个元素的堆上的n个操作的序列，它的大小会增加

from n to 2*n

渐近是…

n=Θ(n)
2*n=Θ(n)

是什么简化了我们的方程式。（我们不必担心 n 的增长，因为它的增长是由常数决定的）。

因此，我们有“ n次插入”操作：

• Xi（n）= X_for_n_insertions（n）
  • Wi（n）=Θ（n lg n）
  • Ai（n）=Θ（n lg n）
  • Bi（n）=Θ（n）
• 对于“所有情况”，这意味着：
  • Ti（n）=Ω（n）和Ti（n）= O（n lg n）

PS要显示ThetaΘ和OmegaΩ符号，您需要安装UTF-8 /才能兼容。