分析堆操作的复杂度
由于堆的实现方式各不相同，因此复杂度也各不相同。堆的一个关键事实是提取操作，从堆中提取最大值或最小值总是需要 \$O(1)\$ 时间。由于我们关注的是二进制堆的实现，因此我们将对二进制堆操作进行分析：
| 操作 | 复杂度平均值 | 复杂度最坏值 |
|---|---|---|
Search |
\$O(n)\$ |
\$O(n)\$ |
Insert |
\$O(1)\$ |
\$O(logn)\$ |
Delete |
\$O(logn)\$ |
\$O(logn)\$ |
Extract |
\$O(1)\$ |
\$O(1)\$ |
Space |
\$O(n)\$ |
\$O(n)\$ |
由于堆没有完全排序，搜索操作所需的时间会比普通二叉搜索树长。