When a priority queue is represented by a max heap containing n elements, the…

Concept: a binary max heap storing n keys is a complete binary tree, so its height is \(\lfloor \log_2 n \rfloor\), that is \(\theta(\log n)\). In a priority queue, deletion means removing the element of highest priority, which in a max heap is the key held at the root. Both updates repair the heap-order property by moving a single key along one root-to-leaf path, so the number of comparisons is governed by the height of the tree and not by the number of keys stored.

Application to the two operations, counted in the worst case as the listed bounds are:

1. Insertion: write the new key in the next free position of the last level so the tree stays complete, then sift it up, exchanging it with its parent while it is the larger of the two. At most one exchange per level gives the upper bound \(O(\log n)\); inserting a key larger than every key already stored forces an exchange at every level, so the walk really does span the height and the worst case is \(\theta(\log n)\).

2. Deletion, that is removing the highest-priority element: take the key at the root, move the last leaf into the root, then sift it down, exchanging it with its larger child while it is the smaller of the two. Again at most one exchange per level gives \(O(\log n)\); when the promoted key is smaller than every key along the path it must follow, it sinks all the way to leaf level, so this worst case is \(\theta(\log n)\) as well.

Cross-check against other representations of the same priority queue, each stated for its own worst case:

Both operations on a max heap therefore run in \(\theta(\log n)\) time in the worst case, and no pair listed among the alternatives states \(\theta(\log n)\) for both, so the answer is “None of the above”. Two habits produce the listed pairs instead: quoting \(\theta(1)\) for deletion, which is really the cost of reading the maximum without removing it, and quoting \(\theta(n)\) for insertion, which is the cost in a representation kept fully sorted. Deleting an arbitrary key whose position is not already known would add a \(\theta(n)\) search on top of the sift, which again states no listed pair.