VietMX Staff asked 4 years ago
Priority Queue abstract data type (ADT) can be implemented using other data structures (including Heaps) like:
- Unordered Array
- Unordered List
- Ordered Array
- Ordered List
- Binary Search Tree (BST)
- Balanced Binary Search Tree (AVL-tree)
- Binary heap
Compare the time efficiency of heap implementation for main operations in Priority Queue ADT with other possible implementations:
----------------------------------------------------------------------------
| Implementation | Insertion | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1 | n | n
----------------------------------------------------------------------------
| Unordered List | 1 | n | n
----------------------------------------------------------------------------
| Ordered Array | n | 1 | 1
----------------------------------------------------------------------------
| Ordered List | n | 1 | 1
----------------------------------------------------------------------------
| BST | logn (avg.) | logn (avg.) | logn (avg.)
----------------------------------------------------------------------------
| Balanced BST | log n | log n | log n
----------------------------------------------------------------------------
| Binary Heaps | log n | log n | 1