Operation | Binary Heap | D-ary Heap | Priority Queue |
---|---|---|---|
Build Heap | O(n) | O(n) | O(n) |
Insert | O(log n) | O(logd n) | O(log n) |
Extract Min/Max | O(log n) | O(d logd n) | O(log n) |
Decrease Key | O(log n) | O(logd n) | N/A |
Get Min/Max | O(1) | O(1) | O(1) |
Delete | O(log n) | O(d logd n) | O(log n) |
Merge | O(n) | O(n) | O(n) |
Implementation | Space Complexity | Additional Notes |
---|---|---|
Binary Heap | O(n) | Complete binary tree structure |
D-ary Heap | O(n) | D children per node |
Priority Queue | O(n) | Additional space for entry objects |