📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    What is the typical time complexity for removing the

    highest-priority element (using poll()) from a java.util.PriorityQueue with N elements?     import java.util.PriorityQueue;     public class HeapQuestion4 {         public static void main(String[] args) {             PriorityQueue pq = new PriorityQueue();             pq.add(10); pq.add(5); pq.add(20); // Assume pq contains N elements             pq.poll(); // What is the time complexity of this operation?         }     }
    A O(1) Correct Answer Incorrect Answer
    B O(log N) Correct Answer Incorrect Answer
    C O(N) Correct Answer Incorrect Answer
    D O(N log N) Correct Answer Incorrect Answer
    E O(N^2) Correct Answer Incorrect Answer

    Solution

    When the highest-priority element (root) is removed from a binary heap (poll() or remove()), the last element in the heap is moved to the root's position. To restore the heap property, this new root element then "bubbles down" (or "heapifies down") by repeatedly swapping with its smallest (or largest, for max-heap) child until its correct position is found. Similar to insertion, this process involves traversing a path from the root to a leaf, which is proportional to the height of the heap. Since the height is O(log N), the time complexity for removal is O(log N).

    Practice Next
    More IT Operating System Questions
    ask-question