📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!
  • google app store apple app store
    • ✖

      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