Queue and Priority Queue Flashcards
(18 cards)
Array Based Implementation
What is the performance of the enqueue method?
Theta 1 (Constant)
Array Based Implementation
What is the performance of the dequeue method?
Theta 1 (Constant)
Array Based Implementation
What is the performance of the peek method?
Theta 1 (Constant)
Array Based Implementation
What is the performance of the size method?
Theta 1 (Constant)
Array Based Implementation
What is the performance of the empty method?
Theta 1 (Constant)
At what end of a list based queue are insertions efficient?
The back
At what end of a list based queue are removals efficient?
The front
List Based Implementation
What is the performance of the enqueue method?
Theta 1 (Constant)
List Based Implementation
What is the performance of the dequeue method?
Theta 1 (Const)
List Based Implementation
What is the performance of the top method?
Theta 1 (Const)
List Based Implementation
What is the performance of the size method?
Theta 1 (Const)
List Based Implementation
What is the performance of the empty method?
Theta 1 (Const)
Which implementation is more expensive in practice?
List based implementation
What is the definition of a min heap?
- It is a full binary tree
- Each child has a value greater than or equal to compared to its parent
How do we add an element to a heap?
- Add an element to the next available space in the array
- Check if the min heap has been violated
- Climb up to the root, making swaps where needed
How do we remove from a heap?
- Swap the minimum and maximum of the heap
- Remove item at end of array as now can be removed safely
- Find good candidates to repair heap by following the path of smaller children
- Climb back up the array, making swaps where needed
What are the main methods of a min heap?
insert
removeMin
What are the worst case runtimes for a min heap’s main methods?
insert: theta (log n)
removeMin: theta (log n)
