For a given priority queue, what is the time complexity to insert a node based…
2021
For a given priority queue, what is the time complexity to insert a node based on some position?
- A.
O(nlogn)
- B.
O(logn)
- C.
O(n2)
- D.
O(n)
- E.
Question not attempted
Attempted by 220 students.
Show answer & explanation
Correct answer: D
To insert a node at a specific position in a priority queue, the algorithm must first place the node at the given position and then restore the heap property by adjusting the structure. This may involve shifting elements up or down the heap. In the worst case, the node may need to be moved from one end of the queue to the other, requiring traversal of all n elements. Therefore, the time complexity is O(n).