Which of the following operations on a priority queue implemented using a…
2026
Which of the following operations on a priority queue implemented using a binary heap requires Θ(log n) time ?
- A.
Checking the size of the queue
- B.
Accessing the minimum element
- C.
Deleting the minimum element
- D.
Creating a heap of n elements
Attempted by 1 students.
Show answer & explanation
Correct answer: C
Concept
In a binary heap of n elements arranged as a complete binary tree, the tree height is Θ(log n). An operation that only touches the root or a counter that is already being maintained runs in Θ(1). An operation that must walk a path from the root down to a leaf (or the reverse) to restore the heap property runs in Θ(log n) per call. Building an entire heap from an unsorted array of n elements is a different kind of operation altogether -- it sums the cost of many such walks across the whole array, and that sum works out to Θ(n), not Θ(log n) or Θ(n log n).
Application
Operation | What it touches | Time |
|---|---|---|
Checking the size of the queue | A maintained counter / the array's length | Θ(1) |
Accessing the minimum element | The root of the min-heap (a single fixed array slot) | Θ(1) |
Deleting the minimum element | Root removed, last leaf moved to the root, then sifted down one level at a time | Θ(log n) |
Creating a heap of n elements | Sift-down run on every internal node, from just above the leaves up to the root | Θ(n) |
Among the four, only deleting the minimum element matches this Θ(log n) cost -- checking the size and accessing the minimum are both Θ(1), and creating a heap of n elements is Θ(n).
Cross-check
This matches two standard, independently-known results: first, the worst-case cost of any single insert or delete-minimum on a binary heap is bounded by the heap's height, so its worst-case time is Θ(log n) -- a call can finish sooner when little or no sifting is needed, but the guaranteed upper bound is Θ(log n), the general worst-case bound behind heap operations. Second, building a heap from n elements bottom-up is a classical Θ(n) result (Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms): even though up to n calls to sift-down are made, most of them act on small subtrees near the leaves, so the total work is linear in n rather than n log n.
So, of the four choices, deleting the minimum element is the operation that requires Θ(log n) time.