| Algorithm | File | buildHeap | clear | decreaseKey | delete | extractMinimum | findMinimum | insert | isEmpty | size | union |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Binary heap | 1 | Θ(n) | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(n) |
| Binomial heap | 1 | Θ(1) | Θ(log n) | O(log n)* | O(log n) | Θ(1) | Θ(1) | Θ(log n) | |||
| Fibonacci heap | 1 | Θ(1)* | Θ(1)* | O(log n)* | O(log n)* | Θ(1) | Θ(1) | Θ(1) | Θ(n) | Θ(1) |
* amortised
| Algorithm | File | add | contains | findMaximum | findMinimum | isEmpty | remove | traverse* | size |
|---|---|---|---|---|---|---|---|---|---|
| Binary search tree | 1 | O(n)** | O(n)** | O(n)** | O(n)** | Θ(1) | O(n)** | Θ(n) | Θ(1) |
| Splay tree | 1 | O(log n)* | O(log n)* | O(n)** | O(n)** | Θ(1) | O(log n)* | Θ(n) | Θ(1) |
* amortised
** O(log n) average