DS
Heap time complexity¶
| Operations | Binary Heap | Binomial Heap | Fibonacci Heap |
|---|---|---|---|
| Procedure | Worst-case | Worst-case | Amortized |
| Making Heap | O(1) | O(1) | O(1) |
| Inserting a node | O(log n) | O(log n) | O(1) |
| Finding Minimum key | O(1) | O(log n) | O(1) |
| Extract-Minimum key | O(log n) | O(log n) | O(log n) |
| Union or merging | O(n) | O(log n) | O(1) |
| Decreasing a Key | O(log n) | O(log n) | O(1) |
| Deleting a node | O(log n) | O(log n) | O(log n) |