Data Structure
Common Operations Running Time
| Search | Select i-th statistic | min/max | rank | successor (next element) | output | insert | deletion | |
|---|---|---|---|---|---|---|---|---|
| Sorted Array (static dataset) | \(\mathcal{\theta}(\log n)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(n)\) | ||
| Binary Search Tree (dynamic dataset) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) |
| Heap | \(\mathcal{O}(1)\) either min or max | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) | |||||
| Hash Table | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) |
Queue
First In, First Out.
Stack
Last In, First Out.
Single linked List
Binary Search Tree
Notes
- A tree diagram where the left descendant is smaller than its parent, the right one is greater than its parent.
- Search operation resembles the binary search in sorted array.
- It can have bad time complexity if it is not balanced. The search can become linear time, not log time. Therefore, Red-Black Tree strategy can be considered.
- Deletion of a node, use left descendant to replace the deleted node.
Min/Max Heap
Notes
- Min Heap, is a tree which has the top node with smallest value, all the descendents are greater than the parents.
- Tree is complete, from top to bottom, from left to right.
- Only need an array, each element is representing one node, from top to bottom and from left to right.
- Extract-Min is constant log time. Get-Min is constant time. Once the top node is deleted, the last element replaces it, and bubble-down to retain the order of heap.
- Insertion to the last leaf, bubble up if necessary.