What are the time complexities for a priority queue implemented with a heap?
2025
What are the time complexities for a priority queue implemented with a heap?
- A.
Insert : θ(log n), Remove : θ(log n)
- B.
Insert : θ(n), Remove : θ(1)
- C.
Insert : θ(1), Remove : θ(log n)
- D.
Insert : θ(log n), Remove : θ(1)
Attempted by 202 students.
Show answer & explanation
Correct answer: A
A binary heap priority queue supports insertion and removal operations in logarithmic time. Inserting an element requires bubbling up to maintain the heap property, taking θ(log n). Removing the root involves bubbling down from the top, also resulting in θ(log n) complexity.