Data Structures
Binary Search Trees
- Insertion: O(log n)
- Deletion: O(log n)
- Search: O(log n)
Queues
- Insertion: O(1)
- Deletion: O(1)
Priority Queues
- Insertion: O(log n)
- Deletion: O(log n)
- degrades to O(n) if Priority Queue becomes unbalanced
- can be implemented as a heap
Heap
- Insertion: O(log n)
- Deletion: O(log n)
- implemented as a complete tree